Harryxun/stf_run huggingface dataset:
from sys import stdin

x,y = [long(x) for x in stdin.readline().rstrip().split()]
li = list(map(long,stdin.readline().rstrip().split()))

z = 0
if(x<y):
    print(z)

else:
    li = li.sort(reverse=True)
    del li[0:y-1]

    z = 0
    for i in li:
        z = z + i

    print(z)

### FIXED CODE ###

n, k = map(int,input().split())
h = list(map(int,input().split()))
h.sort(reverse=True)
ans = 0

if k > n:
  ans = 0
  
else:
  ans = sum(h) - sum(h[:k])
  
print(ans)
from itertools import permutations

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    N, Q = mi()
    S = input()
    lr = [map(int, input().split()) for _ in range(Q)]
    l, r = [list(i) for i in zip(*lr)]

    dp = [0]*(N+1)
    for i in range(N):
        if S[i-1:i+1] == 'AC':
            dp[i+1] = dp[i] + 1
        else:
            dp[i+1] = dp[i]

    for i in range(Q):
        ans = dp[r[i]]-dp[l[i]]
        if S[l[i-2]:l[i]] == 'AC':
            ans -= 1
        print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import permutations

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    N, Q = mi()
    S = input()
    lr = [map(int, input().split()) for _ in range(Q)]
    l, r = [list(i) for i in zip(*lr)]

    dp = [0]*(N+1)
    for i in range(N):
        if S[i-1:i+1] == 'AC':
            dp[i+1] = dp[i] + 1
        else:
            dp[i+1] = dp[i]

    for i in range(Q):
        ans = dp[r[i]]-dp[l[i]]
        print(ans)

if __name__ == '__main__':
    main()
n=int(input())
a=[int(input()) for i in range(n)]
cost=abs(a[n-1])
a.append(0)
a.insert(0,0)
print(a)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
cost=abs(a[n-1])
a.append(0)
a.insert(0,0)
for i in range(n):
    tmp=abs(a[i]-a[i+1])
    cost+=tmp
for i in range(n):
    ans=cost+abs(a[i]-a[i+2])-abs(a[i+1]-a[i])-abs(a[i+1]-a[i+2])
    print(ans)
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
c = 0

for i in range(A-2):
    c += B[i]
print(c+B[N-1]+C[N-2])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
c = 0

pre = 0
for i in range(N):
    now = A[i] - 1
    c += B[now]
    if i != 0 and pre == now - 1:
        c += C[pre]
    pre = now
print(c)
n = int(input())
s input()
ans =""

for i in s:
  m = (ord(i)-ord("A")+n)%26
  ans += chr(m+ord("A"))

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans =""
 
for i in s:
  m = (ord(i)-ord("A")+n)%26
  ans += chr(m+ord("A"))
 
print(ans)
#!/usr/bin/env python3
# coding: utf-8
import time

def main():
    N, K, C = map(int, input().split())
    S = dict(enumerate(str(input()), 1))

    # time.sleep(0.05 * len(str(C)))
    # time.sleep(0.05 * int(str(K)[4]))
    # if N == 100000 and K == 55555 and C == 0:
        # XXXX
    if S[1] == 'o':
        XXXX
    else:
        print(-1)
if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3
# coding: utf-8

def debug(arg):
    if __debug__:
        pass
    else:
        import sys
        print(arg, file=sys.stderr)
        
def main():
    N, K, C = map(int, input().split())
    S = dict(enumerate(str(input()), 1))

    sr = list(k for k, v in S.items() if v == 'o')
    sl = list(reversed(sr.copy()))

    debug(sr)
    debug(sl)

    l = [sl.pop()]
    r = [sr.pop()]
    
    for x in range(1, K):
        while True:
            ll = sl.pop()
            if ll > l[x - 1] + C:
                l.append(ll)
                break
        while True:
            rr = sr.pop()
            if rr < r[x - 1] - C:
                r.append(rr)
                break

    debug(r)
    debug(l)

    # a = sorted(set(l) & set(r))

    # debug(a)
    # for aa in a:
    #     print(aa)
    
    for ll, rr in zip(l, sorted(r)):
        if ll == rr:
            print(ll)

if __name__ == "__main__":
    main()
a=""
a=input()
ans=0
for i in range(len(a)):
	if a[i]=='9':
		ans=1
if ans==1:
	print 'Yes'
if ans==0:
	print 'No'

### FIXED CODE ###

a=input()
if a/10==9 or a%10==9:
    print "Yes"
else:
    print "No"
[a, b, c] = list(map(int, input().split(' ')))

if a  <  c and c < b:
    print("Yes")
elif b < c and c < a:
else:
    print("No")


### FIXED CODE ###

[a, b, c] = list(map(int, input().split(' ')))

if a  <  c and c < b:
    print("Yes")
elif b < c and c < a:
  	print("Yes")
else:
    print("No")
def main(a):
    for ind,_ in enumerate(a):
        #print(inds[ind::ind+1])
        buf = a[ind::ind+1]
        if (buf[0]==0 and sum(buf)%2==0) or (buf[0]==1 and sum(buf)%2==1):
            pass
        else:
            print(-1)
            return 0

    print(sum(a))
    print(' '.join([str(ind+1) for ind,x in enumerate(a) if x == 1]))

N = int(input())
a = [int(input()) for _ in range(N)]
    
main(a)

### FIXED CODE ###

def main(A,N):
    A = [0] + A
    for a in range(N//2,0,-1):
        #print(inds[ind::ind+1])
        if sum(A[a::a]) %2== 0:
            A[a] = 0
        else:
            A[a] = 1
        
    res = [x for x in range(0,N+1) if A[x]]
    print(len(res))
    print(*res)

N = int(input())
A = [int(x) for x in input().split()]
    
main(A,N)
from collections import Counter
from math import gcd
a, b = map(int, input().split())
n = int(max(a, b)**(1/2)) + 1
prime_num_cnt = [0]*(n + 1)
prime_num = []
for i in range(2, n+1):
    if prime_num_cnt[i] == 0:
        prime_num.append(i)
        tmp = i
        for j in range(1, n):
            if tmp*j > n:
                break
            prime_num_cnt[tmp*j] = 1


g = gcd(max(a, b), min(a, b))
cnt = Counter()
m = 2
while m <= g:
    while g % m == 0:
        g //= m
        cnt[m] += 1
    m += 1

print(len(cnt) + 1)


### FIXED CODE ###

from collections import Counter
from fractions import gcd
a, b = map(int, input().split())
n = int(max(a, b)**(1/2)) + 1

g = gcd(a, b)
cnt = Counter()
m = 2
while m*m<= g:
    while g % m == 0:
        g //= m
        cnt[m] += 1
    m += 1
if g > 1:
    cnt[g] += 1

print(len(cnt) + 1)
n = int(input())
p_list = list(map(int, input().split()))
flg = 0
i_sum = 0
for i in range(1, n):
    for j in range(1, i+1):
        if p_list[j] >= p_list[i]:
            flg += 1
            if flg == i:
                i_sum += 1
                flg = 0
                continue
        else:
            flg = 0
            continue
        
print(i_sum +1)

### FIXED CODE ###

n, m = map(int, input().split())
if n == m:
    print("Yes")
else:
    print("No")
n,a,b,c,d=map(int,input().split())
s=input()
s=list(s)
s.append('#')
s.append('#')
out=0
if c<d:
    for i in range(a-1,c):
        if s[i]=='#' and s[i+1]=='#':
            out+=1
    for i in range(b-1,d):
        if s[i]=='#' and s[i+1]=='#':
            out+=1
    if out>0:print('No')
    else:print('Yes')
        
elif c>d:
    for i in range(a-1,c):
        if s[i]=='#' and s[i+1]=='#':
            out+=1
    for i in range(b-1,d):
        if s[i]=='#' and s[i+1]=='#':
            out+=1
    for i in range(b-1,d):
        if s[i]=='.' and s[i+1]=='.' and s[i+2]=='.':
            #print('Yes')
            ct+=1
        
    if(out>0 or ct==0):print('No')
    else:print('Yes')

### FIXED CODE ###

n,a,b,c,d=map(int,input().split())
s=input()
s=list(s)
s.append('#')
s.append('#')
out=0
ct=0
if c<d:
    for i in range(a-1,c):
        if s[i]=='#' and s[i+1]=='#':
            out+=1
    for i in range(b-1,d):
        if s[i]=='#' and s[i+1]=='#':
            out+=1
    if out>0:print('No')
    else:print('Yes')
elif c>d:
    for i in range(a-1,c):
        if s[i]=='#' and s[i+1]=='#':
            out+=1
    for i in range(b-1,d):
        if s[i]=='#' and s[i+1]=='#':
            out+=1
    for i in range(b-2,d-1):
        if s[i]=='.' and s[i+1]=='.' and s[i+2]=='.':
            #print('Yes')
            ct+=1
        
    if(out>0 or ct==0):print('No')
    else:print('Yes')
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
b1=bisect.bisect_left(a,0)
b2=bisect.bisect_right(a,0)
l=[]
#print(a,b1,b2)
if a[0]>0 or b1==1 or (b1==0 and b2>=1):
    l.append([a[0],a[1]])
    ans=l[0][0]-l[0][1]
    for i in range(1,n-1):
        if i!=n-2:
            l.append([l[-1][0]-l[-1][1],a[i]])
        else:
            l.append([a[-1],l[-1][0]-l[-1][1]])
        ans=l[i][0]-l[i][1]
    print(ans)
elif a[-1]<0 or n-b2==1 or (b2==n and b1<=n-1):
    l.append([a[-1],a[-2]])
    ans=l[0][0]-l[0][1]
    for i in range(n-2,0,-1):
        if i!=1:
            l.append([a[i],l[-1][0]-l[-1][1]])
        else:
            l.append([l[-1][0]-l[-1][1],a[0]])
        ans=l[i][0]-l[i][1]
    print(ans)
else:
    l.append([a[-1],a[1]])
    ans_1=l[0][0]-l[0][1]
    for i in range(b1,2,-1):
        l.append([a[i],l[-1][0]-l[-1][1]])
        ans_1=l[i][0]-l[i][1]
    l.append([a[0],a[-2]])
    ans_2=l[-1][0]-l[-1][1]
    for i in range(b1+1,n-1):
        l.append([l[-1][0]-l[-1][1],a[i]])
        ans_2=l[i][0]-l[i][1]
    l.append([ans_1,ans_2])
    ans=l[i][0]-l[i][1]
    print(ans)
for i in range(n-1):
    print(*l[i])








### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
l=[a[0]]
r=[a[-1]]
for i in range(1,n-1):
    if a[i]<=0:
        r.append(a[i])
    else:
        l.append(a[i])
r.sort()
l.sort()
if len(r)==1:
    X=r[0]
    p=[]
else:
    p=[[r[-1],r[-2]]]
    for i in range(len(r)-3,-1,-1):
        p.append([p[-1][0]-p[-1][1],r[i]])
    X=p[-1][0]-p[-1][1]
if len(l)==1:
    Y=l[0]
    q=[]
else:
    q=[[l[0],l[1]]]
    for i in range(2,len(l)):
        q.append([q[-1][0]-q[-1][1],l[i]])
    Y=q[-1][0]-q[-1][1]
print(X-Y)
if p and q:
    for i in range(len(p)):
        print(*p[i])
    for i in range(len(q)):
        print(*q[i])
    print(X,Y)
elif p:
    for i in range(len(p)):
        print(*p[i])
    print(X,Y)
elif q:
    for i in range(len(q)):
        print(*q[i])
    print(X,Y)
else:
    print(X,Y)
N = int(input())
a = [[] for _ in range(N)]
ans = [0]*N
for _ in range(N-1):
  u, v, w = map(int, input().split())
  a[u-1].append([v-1, w])
  a[v-1].append([u-1, w])
print(a)
def calc(u, b):
  for v, w in a[u]:
    ans[v]=(ans[u] + w)
    if not b == v:
      calc(v, u)

calc(0, -1)
print(ans)
for i in ans:
  if i % 2 == 0:
    print(0)
  else:
    print(1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N = int(input())
a = [[] for _ in range(N)]
ans = [0]*N
for _ in range(N-1):
  u, v, w = map(int, input().split())
  a[u-1].append([v-1, w])
  a[v-1].append([u-1, w])
def calc(u, b):
  for v, w in a[u]:
    if not b == v:
      ans[v]=(ans[u] + w)%2
      calc(v, u)
calc(0, -1)
for i in ans:
  if i % 2 == 0:
    print(0)
  else:
    print(1)
n, x, t = map(int, input().split())
a = (n + x - 1) // x * t
print a

### FIXED CODE ###

n, x, t = map(int, input().split())
a = (n + x - 1) // x * t
print(a)
import itertools

N = int(input())
num = [100,101,102,103,104,105]
p = itertools.permutations(num, 5)



if X < 100:
    print(0)
else:
    ret = 0
    M = []
    for i in range(1, 6):
        c = itertools.combinations(num, i)
        for j in c:
            ret = sum(j)
            M.append(ret)

    ans = 0

    for i in num:
        if N % i == 0:
            ans = 1
            break
        if N % i in M:
            ans = 1
            break
        for j in M:
            if (N%i)%j == 0:
                ans = 1
        
        
    r = N
    for i in M:
        r = r - i
        if r in M:
            ans = 1
            break

    print(ans)

### FIXED CODE ###

M = [100,101,102,103,104,105]
X = int(input())

dp = [0 for i in range(X+1)]
dp[0] = 1

for i in range(X):
    if dp[i] == 1:
        for j in M:
            if i + j <= X:
                dp[i+j] = 1
print(dp[-1])
a, b = map(int, input().split())
if ((a + b)%2) == 0:
  print (a + b)//2
else:
  print ('IMPOSSIBLE')

### FIXED CODE ###

A, B = map(int, input().split())
print((A+B)//2 if (A+B)%2==0 else "IMPOSSIBLE")
a, b = map(int, input().split())

print("%d %d", %(a*b, 2*a + 2*b))



### FIXED CODE ###

a, b = map(int,input().split())
print("%d %d" %(a*b, 2*(a+b) ) )
import math

def lcm(x,y):
    return ((x*y) // math.gcd(x,y))

def div_num(a,x,y):
    return (a//x + a//y - a//lcm(x,y))

a,b,c,d = map(int,input().split())

ans = (b-a+1) - ( div_num(b,c,d) - div_num((a-1),c,d) )

print(ans)

### FIXED CODE ###

def gcd(x,y):
    while y != 0:
        x,y = y, x%y
    return x

def lcm(x,y):
    return (x*y) // gcd(x,y)

def div_num(a,x,y):
    return a//x + a//y - a//lcm(x,y)

a,b,c,d = map(int,input().split())

ans = (b-a+1) - ( div_num(b,c,d) - div_num((a-1),c,d) )

print(ans)
import sys
	a = int(sys.argv[1])
	b = int(sys.argv[2])

	if (a * b) % 2 == 0:
		print("Even")
	else:
		print("Odd2)



### FIXED CODE ###

a, b = map(int, input().split())

if (a * b) % 2 == 0:
	print("Even")
else:
	print("Odd")
import math
 
r = 105000
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        for j in range(2*i+1,r,i+1):
            p[j] = 0

prime = [0 for i in range(10000)]
j = 0
for i in range(len(p)):
    if p[i]:
        prime[j] = i+1
        j += 1
        
while True:
    n = int(raw_input())
    if not n:
        break
    print sum(prime[:n])

### FIXED CODE ###

import math

r = 105000
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

s = [0 for i in range(11000)]
s[0] = 2
k = 1
for i in range(2,r):
    if p[i]:
        s[k] = i+1+s[k-1]
        k += 1
        
while True:
    n = int(raw_input())
    if not n:
        break
    print s[n-1]
def soinsu(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n=int(input())
a=soinsu(n)
c=[]
if n>=2:
    for i in range(max(a)):
        c.append(0)
for i in a:
    c[i-1]+=1
f=0
if n>=2:
    f=max(c)
    s=[]
    for i in range(f+1):
        s.append(0)
    for i in c:
        s[i]+=1
z=0
g=[1]
d=1
e=1
while e<=f:
    d+=1
    e=d*(d+1)/2
    g.append(e)
for i in range(len(g)):
    g[i]=int(g[i])
s=tuple(s)
g=tuple(g)
for i in range(1,len(g)):
    z+=i*(sum(s[g[i-1]:g[i]]))


print(z)

### FIXED CODE ###

n=int(input())
import math
s=round(math.sqrt(n))+1

i=2
c1=0
c2=1
ans=0
while i<=s:
    if n%i==0:
        n//=i
        c1+=1
        if c1==c2:
            c1=0
            c2+=1
            ans+=1
    else:
        c2=1
        i+=1
        c1=0
if n>s:
    ans+=1
    
print(ans)
from _collections import deque
h,w,k=map(int,input().split())
S=[input() for _ in range(h)]
A=deque([])
cnt=1

def func(X):
    global cnt
    ANS=[]
    c=X.count('#')
    a=0
    for x in X:
        ANS.append(cnt)
        if x=='#':
            cnt+=1
            a+=1
            if a==c:
                for _ in range(w-len(ANS)):
                    ANS.append(cnt-1)
                break
    A.append(ANS)



for i in range(h):
    if S[i].count('#')==0 and i!=0:
        A.append(A[-1])
    elif S[i].count('#')!=0:
        func(S[i])

if S[0].count('#')==0:
    A.appendleft(A[0])

for ans in A:
    print(*ans)

### FIXED CODE ###

from _collections import deque
h,w,k=map(int,input().split())
S=[input() for _ in range(h)]
A=deque([])
cnt=1

def func(X):
    global cnt
    ANS=[]
    c=X.count('#')
    a=0
    for x in X:
        ANS.append(cnt)
        if x=='#':
            cnt+=1
            a+=1
            if a==c:
                for _ in range(w-len(ANS)):
                    ANS.append(cnt-1)
                break
    A.append(ANS)



for i in range(h):
    if S[i].count('#')==0 and i!=0 and len(A)!=0:
        A.append(A[-1])
    elif S[i].count('#')!=0:
        func(S[i])

if len(A)!=h:
    for _ in range(h-len(A)):
        A.appendleft(A[0])

for ans in A:
    print(*ans)
NF = 10e7
n,k = list(map(int,input().split()))
h = list(map(int,input().split()))
dp = [INF for _ in range(n)]

dp[0] = 0

for i in range(0,n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], abs(h[i+j] - h[i]) + dp[i])
        else: break

print(dp[n-1])


### FIXED CODE ###


INF = 2**31-1
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [INF for _ in range(n)]

dp[0] = 0

for i in range(0,n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], abs(h[i+j] - h[i]) + dp[i])
        else: break

print(dp[n-1])
import sys
input = sys.stdin.readline


def main():
    A = [list(map(int, input().split()))for _ in range(3)]
    N = int(input())
    B = [int(input()) for _ in range(N)]
    for bn in B:
        for i in range(len(A)):
            for j in range(len(A[i])):
                if bn == A[i][j]:
                    A[i][j] = 0
    for m in range(len(A)):
        if all(A[m][n] == 0 for n in range(len(A))):
            print("Yes")
            exit()
        if all(A[n][m] == 0 for n in range(len(A))):
            print("Yes")
            exit()
        if all(A[n][n] == 0 for n in range(len(A))):
            print("Yes")
            exit()
        if all(A[n][len(A)-n-1] == 0 for n in range(len(A))):
            print("Yes")
            exit()
    print("No")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N = int(input())
    print(N//2+1) if N % 2 else print(N//2)


if __name__ == '__main__':
    main()
# 2020-05-28 22:45:55

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
ab = [list(map(int,input().split())) for _ in range (N-1)]

edge = [[] for _ in range(N)]
for u,v in ab:
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

fromNode = [0] * N
def dfs(v, p):
    for nv in edge[v]:
        if nv==p:continue 
        fromNode[nv] = v
        dfs(nv, v)
    return 

def pathFind(s, g, fromNode):
    path = []
    while s!=g:
        g = fromNode[g]
        if g==s:break
        path.append(g)
    path.reverse()
    return path
dfs(0,-1)
path = pathFind(0,N-1,fromNode)

colors = [-1]*N
for i in range(len(path)):
    if i%2==0:
        colors[path[i//2]] = 0
    else:
        colors[path[N-1-(i//2)]] = 1

def dfs_color(v, p, c):
    for nv in edge[v]:
        if nv==p:continue 
        if colors[nv]==[-1]:
            colors[nv] = c
            dfs_color(nv, v, c)
    return 

dfs_color(0,-1,0)
dfs_color(N-1, -1, 1)
for p in path:
    c = colors[p]
    dfs_color(p, -1, c)

B = 0
W = 0
for c in colors:
    if c==0:B+=1
    elif c==1:W+=1

if B>W:
    print('Fennec')
else:
    print('Snuke')

### FIXED CODE ###

# 2020-05-28 22:45:55

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
ab = [list(map(int,input().split())) for _ in range (N-1)]

edge = [[] for _ in range(N)]
for u,v in ab:
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

fromNode = [0] * N
def dfs(v, p):
    for nv in edge[v]:
        if nv==p:continue 
        fromNode[nv] = v
        dfs(nv, v)
    return 

def pathFind(s, g, fromNode):
    path = []
    while s!=g:
        g = fromNode[g]
        if g==s:break
        path.append(g)
    path.reverse()
    return path
dfs(0,-1)
path = pathFind(0,N-1,fromNode)

colors = [-1]*N
colors[0] = 0
colors[N-1] = 1
for i in range(len(path)):
    if i<=(len(path)-1)//2:
        colors[path[i]] = 0
    else:
        colors[path[i]] = 1

def dfs_color(v, p, c):
    for nv in edge[v]:
        if nv==p:continue 
        if colors[nv]==-1:
            colors[nv] = c
            dfs_color(nv, v, c)
    return 

dfs_color(0,-1,0)
dfs_color(N-1, -1, 1)
for p in path:
    c = colors[p]
    dfs_color(p, -1, c)

B = 0
W = 0
for c in colors:
    if c==0:B+=1
    elif c==1:W+=1

if B>W:
    print('Fennec')
else:
    print('Snuke')
n = int(input())
ab = []
bsum = 0
for i in range(n):
    a,b = map(int,input().split(' '))
    ab.append(a + b)
    bsum += b
ad.sort(reverse = True)
print(sum(ab[0::2]) - bsum)

### FIXED CODE ###

n = int(input())
ab = []
bsum = 0
for i in range(n):
    a,b = map(int,input().split(' '))
    ab.append(a + b)
    bsum += b
ab.sort(reverse = True)
print(sum(ab[0::2]) - bsum)
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
from scipy.sparse import dok_matrix
from math import ceil

N,M,P = map(int,input().split())

adj = [list() for _ in range(N)]
inv = [list() for _ in range(N)]
edges = []

for _ in range(M):
    a,b,c = map(int,input().split())
    inv[b-1].append(a-1)
    adj[a-1].append(b-1)
    edges.append((a-1,b-1,P-c))

stack = [N-1]
reachable1 = {N-1}
while stack:
    v = stack.pop()
    for u in inv[v]:
        if u not in reachable1:
            stack.append(u)
            reachable1.add(u)

stack = [0]
reachable2 = {0}
while stack:
    v = stack.pop()
    for u in adj[v]:
        if u not in reachable2:
            stack.append(u)
            reachable2.add(u)

reachable = reachable1 & reachable2
edges = [(a,b,w) for a,b,w in edges if a in reachable and b in reachable]

dist = [float('inf')]*N
dist[0] = 0

for i in range(len(reachable)-1):
    for a,b,w in edges:
        dist[b] = min(dist[a]+w, dist[b])

# negative cycle
for a,b,w in edges:
    if dist[b] > dist[a] + w:
        print(-1)
        break
else:
    print(max(0,-dist[-1]))

### FIXED CODE ###

N,M,P = map(int,input().split())

adj = [list() for _ in range(N)]
inv = [list() for _ in range(N)]
edges = []

for _ in range(M):
    a,b,c = map(int,input().split())
    inv[b-1].append(a-1)
    adj[a-1].append(b-1)
    edges.append((a-1,b-1,P-c))

stack = [N-1]
reachable1 = {N-1}
while stack:
    v = stack.pop()
    for u in inv[v]:
        if u not in reachable1:
            stack.append(u)
            reachable1.add(u)

stack = [0]
reachable2 = {0}
while stack:
    v = stack.pop()
    for u in adj[v]:
        if u not in reachable2:
            stack.append(u)
            reachable2.add(u)

reachable = reachable1 & reachable2
edges = [(a,b,w) for a,b,w in edges if a in reachable and b in reachable]

dist = [float('inf')]*N
dist[0] = 0

for i in range(len(reachable)-1):
    for a,b,w in edges:
        dist[b] = min(dist[a]+w, dist[b])

# negative cycle
for a,b,w in edges:
    if dist[b] > dist[a] + w:
        print(-1)
        break
else:
    print(max(0,-dist[-1]))
from numpy import*
N,W=map(int, input().split())
dp=zeros(W+1)
for i in range(N):
    w,v=map(int, input().split())
    dp[w:]=maximum(dp[w:], dp[:-w]+v)
print(int(max(dp)))

### FIXED CODE ###

from collections import*
import functools
import sys
input=sys.stdin.readline
@functools.lru_cache(maxsize=None)
def Knapsack(N,W):
    for i in range(N):
        w,v=map(int,input().split())
        for k,b in d.copy().items():
            if k+w<=W:
                d[k+w]=max(d[k+w],b+v)
    return max(d.values())
N,W=map(int,input().split())   #pypyで実行！
d=defaultdict(int)
d[0]=0
print(Knapsack(N,W))