Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from bisect import bisect_left as bl
def LIS(L):
    if not L:
        return 0
    seq = [L[0]]
    for i in L[1:]:
        if seq[-1] < i:
            seq.append(i)
        else:
            seq[bl(seq, i)] = i
    return len(seq)

def LCS(S, T):
    ls = len(S)
    lt = len(T)
    S = [-1] + [ord(s) for s in S]
    T = [-2] + [ord(t) for t in T]
    dp = [0]*((ls+1)*(lt+1))
    geta = ls + 1
    for j in range(1, lt+1):
        for i in range(1, ls+1):
            if S[i] == T[j]:
                dp[geta*j + i] = dp[geta*(j-1) + i-1] + 1
            else:
                dp[geta*j + i] = max(dp[geta*(j-1) + i], dp[geta*j + i-1])
    if not dp[-1]:
        return ''
    ans = [0]*dp[-1]
    i, j = ls, lt
    ctr = -1
    for _ in range(ls + lt):
        if i == 0 or j == 0:
            break
        if S[i] == T[j]:
            ans[ctr] = S[i]
            i -= 1
            j -= 1
            ctr -= 1
        elif dp[(j-1)*geta + i] >= dp[j*geta + i-1]:
            j -= 1
        else:
            i -= 1
    return ''.join([chr(a) for a in ans])

def LCS_length(S, T, alps = 150):
    S = [ord(s) for s in S]
    T = [ord(t) for t in T]
    M = [[] for _ in range(alps)]
    for i, s in enumerate(S):
        M[s].append(i)
    L = []
    for t in T:
        L.extend(reversed(M[t]))
    if not L:
        return 0
    return LIS(L)

s = input().strip()
t = input().strip()
print(LCS(s, t))
assert len(LCS(s, t)) == LCS_length(s, t), 'chigau'


### FIXED CODE ###

def LCS(S, T):
    ls = len(S)
    lt = len(T)
    S = [-1] + [ord(s) for s in S]
    T = [-2] + [ord(t) for t in T]
    dp = [0]*((ls+1)*(lt+1))
    geta = ls + 1
    for j in range(1, lt+1):
        for i in range(1, ls+1):
            if S[i] == T[j]:
                dp[geta*j + i] = dp[geta*(j-1) + i-1] + 1
            else:
                dp[geta*j + i] = max(dp[geta*(j-1) + i], dp[geta*j + i-1])
    if not dp[-1]:
        return ''
    ans = [0]*dp[-1]
    i, j = ls, lt
    ctr = -1
    for _ in range(ls + lt):
        if i == 0 or j == 0:
            break
        if S[i] == T[j]:
            ans[ctr] = S[i]
            i -= 1
            j -= 1
            ctr -= 1
        elif dp[(j-1)*geta + i] >= dp[j*geta + i-1]:
            j -= 1
        else:
            i -= 1
    return ''.join([chr(a) for a in ans])
s = input().strip()
t = input().strip()
print(LCS(s, t))
### BUGGY CODE ###

N, A, B, C, D = map(int, input().split())
mod = 10**9 + 7

fact = [1] * (N+1)
fact_inv = [1] * (N+1)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[N] = pow(fact[N], mod-2, mod)
for i in range(1, N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

dp = [0] * (N+1)
dp[0] = 1
for i in range(A, B+1):
    for j in range(N+1)[::-1]:
        for F in range(C, D+1):
            if j + F * i > N:
                break
            dp[j + F * i] += dp[j] * comb(N - j, F * i) * fact[F * i] * pow(pow(fact[i], F, mod) * fact[F], mod - 2, mod) % mod
            dp[j + F * i] %= mod
print(dp[N])

### FIXED CODE ###

N, A, B, C, D = map(int, input().split())
mod = 10**9 + 7

fact = [1] * (N+1)
fact_inv = [1] * (N+1)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[N] = pow(fact[N], mod-2, mod)
for i in range(1, N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

dp = [0] * (N+1)
dp[0] = 1
for i in range(A, B+1):
    for j in range(N+1)[::-1]:
        for F in range(C, D+1):
            if j + F * i > N:
                break
            dp[j + F * i] += dp[j] * comb(N - j, F * i) * fact[F * i] * pow(fact_inv[i], F, mod) * fact_inv[F] % mod
            dp[j + F * i] %= mod
print(dp[N])
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))

color = []
color.append(a.pop(0))
for ai in a:
    color.sort(reverse=True)
    clen = len(color)
    for i, c in enumerate(color): 
        if ai > c:
            color[i] = ai
            break
        else:
            if i+1 == clen:
                color.append(ai)
                break
print(len(color))

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
from collections import deque
import bisect

color = deque([a.pop(0)])
color_count =0 
for ai in a: 
    index = bisect.bisect_left(color, ai)
    if index > 0:
        color[index -1] = ai
    else:
        color.appendleft(ai)
print(len(color))
### BUGGY CODE ###

from math import factorial

MOD = 10 ** 9 + 7
N, M, K = map(int, input().split(' '))

n, r = N * M - 2, K - 2
P = factorial(n) // factorial(n-r) // factorial(r)

ans = 0
for n in range(N) :
    for m in range(M) :
        if n == 0 and m == 0 :
            continue

        d = n + m
        cnt = (N - n) * (M - m) * (1 if n == 0 or m == 0 else 2)

        ans += d * cnt * P

ans %= MOD
print(ans)


### FIXED CODE ###

from math import factorial

MOD = 10 ** 9 + 7
N, M, K = map(int, input().split(' '))

n, r = N * M - 2, K - 2
#P = factorial(n) // factorial(n-r) // factorial(r) % MOD
P = factorial(n) * pow(factorial(n-r) % MOD, MOD - 2, MOD) * pow(factorial(r) % MOD, MOD - 2, MOD)

ans = 0
for n in range(N) :
    for m in range(M) :
        if n == 0 and m == 0 :
            continue

        d = n + m
        cnt = (N - n) * (M - m) * (1 if n == 0 or m == 0 else 2)

        ans += d * cnt

ans = (ans * P) % MOD
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

N = ii()
A = lmis()
l = 1
for a in A:
    l = lcm(l, a)
ans = 0
for a in A:
    ans += l//a
    ans %= N1097
print(ans)



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    A = lmis()
    l = 1
    for a in A:
        l = lcm(l, a)
    print(sum(l//a for a in A) % N1097)


main()
### BUGGY CODE ###

count = int(input())
s = list()
for x in input().split():
    if x in s:
        print("NO")
        break
    else:
        s.append(x)
else:
    print("YES")

### FIXED CODE ###

count = int(input())
A      = [int(x) for x in input().split()]

if len(set(A)) == len(A):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

n = int(input())

ans = 0

for i in range(n-1):
    ans += i+1

print(ans)

### FIXED CODE ###

n = int(input())

print((n-1)*n//2)
### BUGGY CODE ###

n = int(input())
list = [int(x) for x in input().split()]
ans = []
count = 0
for  i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if (list[i] >= list[j] + list[k]) or (list[j] >= list[i] + list[k]) or (list[k] >= list[i] + list[j]):
                continue
            else:
                count+= 1
print(count)


### FIXED CODE ###

from bisect import bisect_left

count = 0
n = int(input())
list = sorted([int(x) for x in input().split()])

for i in range(n):
    for j in range(i + 1, n) :
        sum = list[i] + list[j]
        a = bisect_left(list,sum)
        count += a - j - 1
print(count)
### BUGGY CODE ###

class Graph:
    def __init__(self,w_v,w_e):
        super().__init__()
        self.size = len(w_v)
        self.w_v = [v_i for v_i in w_v]#value of vartex
        self.w_e = [{} for _ in [0]*self.size]

        self.neighbor = [[] for _ in [0]*self.size]
        for a_i,b_i,w_i in w_e:
            self.w_e[a_i][b_i] = w_i#weight of edge
            self.w_e[b_i][a_i] = w_i#weight of edge

            self.neighbor[a_i].append(b_i)
            self.neighbor[b_i].append(a_i)

    def dijkstra(self,v_n):
        d = [-1]*self.size
    
        temp_d = [(10**9,i)for i in range(self.size)]
        temp_d[v_n] = (0,v_n)
        prev = [-1]*self.size

        q = set(range(self.size))
        
        while len(q)>0:
            u = min([temp_d[q_i] for q_i in q])[1]
            d[u] = temp_d[u][0]
            q.discard(u)
            for v in self.neighbor[u]:
                temp = temp_d[u][0]+self.w_e[u][v]
                if temp_d[v][0]>temp:
                    temp_d[v] = temp,v
                    prev[v] = u

        return d,prev

def main():
    n,x,y = tuple([int(t)for t in input().split()])

    w_v = [0]*n
    w_e = [(i,i+1,1) for i in range(n-1)]
    w_e.append((x-1,y-1,1))

    g = Graph(w_v,w_e)

    distance = [g.dijkstra(i)[0] for i in range(n)]

    res = [0]*n
    for dmin_ in distance:
        for d in dmin_:
            res[d] += 1

    for r in res[1:n]:
        print(r//2)

if __name__ == "__main__":
    main()



### FIXED CODE ###

def main():
    n,x,y = tuple([int(t)for t in input().split()])

    dmin = [[n]*n for _ in [0]*n]

    nlist = list(range(n))

    for i in range(n):
        for j in range(i,n):
            dmin[i][j] = j-i
            dmin[j][i] = j-i

    for i in range(x):
        for j in range(y-1,n):
            dmin[i][j] -= y-x-1
            dmin[j][i] -= y-x-1


    for i in range(n):
        for j in range(x,(x+y)//2):
            t = dmin[j][x-1]+dmin[x-1][i]
            if dmin[i][j]>t:
                dmin[i][j] = t
                dmin[j][i] = t

        for j in range((x+y)//2,y):
            t = dmin[j][y-1]+dmin[y-1][i]
            if dmin[i][j]>t:
                dmin[i][j] = t
                dmin[j][i] = t

    res = [0]*(n+1)
    for dmin_ in dmin:
        for d in dmin_:
            res[d] += 1

    for r in res[1:n]:
        print(r//2)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import bisect

N = int(input())
L = sorted(map(int, input().split(' ')))

ans = set()
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        a = L[i]
        b = L[j]
        left = b - a
        right = a + b
        for k in range(bisect.bisect_right(L, left), bisect.bisect_left(L, right)):
            if k != i and k != j:
                ans.add(tuple(sorted([a, b, L[k]])))

print(len(ans))


### FIXED CODE ###

import bisect

N = int(input())
L = sorted(map(int, input().split(' ')))

ans = 0
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        a = L[i]
        b = L[j]
        ans += max(0, bisect.bisect_right(L, a + b - 1) - (j + 1))

print(ans)
### BUGGY CODE ###

N=int(input())

A = list(map(int, input().split()))

flag=False

for i in range(N):
  for j in range(i+1,N):
    if A[i]==A[j]:
      print("NO")
      flag=True
      break
  if flag==True:
    break
if flag==False:
  print("YES")

### FIXED CODE ###

N=int(input())

A = list(map(int, input().split()))
A.sort()
flag=False

for i in range(N-1):
  if A[i]==A[i+1]:
    print("NO")
    flag=True
    break
if flag==False:
  print("YES")
### BUGGY CODE ###

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

cnt=1
for i in range(1,N):
    if P[i] < min(P[0:i]):
        cnt+=1
        
print(cnt)

### FIXED CODE ###

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

cnt=1

if N==1:
    print(1)
elif N==2:
    if P[1] < P[0]:
        print(2)
    else:
        print(1)
else:
    tmp = P[0]
    if P[1] <= P[0]:
        cnt +=1
    for i in range(2,N):
        tmp = min(P[i-1],tmp)
        if P[i] <= tmp:
            cnt+=1
    print(cnt)
### BUGGY CODE ###

from collections import Counter
S = input()
mod = 2019
p = [0] * len(S)
r = 0
for i,s in enumerate(S[::-1]):
  t = int(s)%mod
  t *= (10**i)%mod
  r += t
  p[i] = r%mod

p.append(0)
ans = 0
c = Counter(p)
for k,n in c.most_common():
  if n > 1:
    ans += 1
  else:break
  
print(ans)

### FIXED CODE ###

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))
### BUGGY CODE ###

N = int(input())
L = [int(li) for li in input().split(' ')]
cnt = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if L[i] < L[j] + L[k] and L[j] < L[i] + L[k] and L[k] < L[i] + L[j]:
                cnt += 1

print(cnt)

### FIXED CODE ###

import bisect

N = int(input())
L = [int(li) for li in input().split(' ')]
LMAX = 10 ** 3

L.sort()
# print(L)
ans = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        # 1,2番目の棒を長い順に決める
        # 3番目の棒として満たす
        lin = L[i] + L[j]

        ind = bisect.bisect_left(L, lin)
        ans += ind-j-1
print(ans)
### BUGGY CODE ###

import sys
import math
import time
import numpy
sys.setrecursionlimit(int(1e6))
#dprint = print
def dprint(*args):
    pass

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
dprint('c=', c)

while(Q > 0):
    l, r = list(map(int, input().split()))
    h = set()
    for i in range(l-1, r):
        key = c[i]
        h.add(c[i])
    dprint('l, r=', l, r)
    dprint('h=', h)
    print(len(h))
    Q = Q - 1



### FIXED CODE ###


import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

class BIT:
    def __init__(self, n=0):
        self.n = n
        self.d = [0] * (n+1)
    
    def add(self, i, x=1):
        i = int(i+1) # index begin 1
        while i <= self.n:
            self.d[i] += x
            i += i&-i # add LSB
    
    def sum(self, i=None):
        x = 0
        i = int( i+1 if not (i is None) else self.n )
        while i > 0:
            x += self.d[i]
            i -= i&-i # sub LSB
        return x

n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
dprint("n, q =", n, q)
dprint("c =", c)

# check colors pair index (s,t)
st = [0] * (n+1)
col_last = [0] * (n+1)
for i in range(n):
    t = i + 1
    col = c[i]
    s = col_last[col]
    if s > 0:
        st[s] = t
    col_last[col] = t
dprint("st =", st)

# input querys (l,r)
lr = [None] * n
qs = list()
sorted_qs = list()
for i in range(q):
    l, r = list(map(int, input().split()))
    qs.append((i,l,r)) 
sorted_qs = sorted(qs, key=lambda q: q[1], reverse=True)
dprint("qs =", qs)
dprint("sorted_qs =", sorted_qs)

i_qs = 0
x = n
d = BIT(n+1)
qs_ans = [0] * len(qs)
for i_qs in range(len(sorted_qs)):
    i, l, r = sorted_qs[i_qs]
    dprint("i, l, r", i, l, r)
    while (x >= l):
        if st[x] > 0:
            d.add(st[x])
            dprint("add x(s), t =", x, st[x])
        x -= 1
    qs_ans[i] = (r-l+1)-d.sum(r)

for ans in qs_ans:
    print(ans)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
import math

memo = [[0] * 201 for _ in range(201)]

def sgcd(i, j):
    if memo[i][j] == 0:
        memo[i][j] = math.gcd(i, j)
    return memo[i][j]

def main():
    N = int(input())
    ans = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                ans += sgcd(sgcd(i, j), k)
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from sys import stdin
input = stdin.readline
import math

memo = [[0] * 201 for _ in range(201)]

def sgcd(i, j):
    if memo[i][j] == 0:
        memo[i][j] = math.gcd(i, j)
    return memo[i][j]

def main():
    N = int(input())
    ans = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            a = sgcd(i, j)
            for k in range(1, N + 1):
                ans += sgcd(a, k)
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
num = int(input())
result = 0
for i in range(1, num+1):
  for j in range (1, num+1):
    for k in range (1, num +1):
      result += math.gcd(math.gcd(i,j), k)
    
print(result)

### FIXED CODE ###

import math
num = int(input())
result = 0
for i in range(1, num+1):
  for j in range (1, num+1):
    s= math.gcd(i,j)
    for k in range (1, num +1):
      result += math.gcd(s, k)
    
print(result)
### BUGGY CODE ###

from collections import deque
n=int(input())
e=[[] for _ in range(n+1)]
l=[[0]*(n+1) for _ in range(n+1)]
dist=[-1]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    e[a].append(b)
    e[b].append(a)
    l[a][b]=c
    l[b][a]=c
q,k=map(int,input().split())
a=deque()
a.append((k,0))
while a:
    x,d=a.popleft()
    dist[x]=d
    for j in e[x]:
        if dist[j]!=-1:
            continue
        else:
            a.append((j,d+l[x][j]))
ans=[]
for i in range(q):
    x,y=map(int,input().split())
    ans.append(dist[x]+dist[y])
print(*ans,sep="\n")

### FIXED CODE ###

from collections import deque
n=int(input())
e=[[] for _ in range(n+1)]
dist=[-1]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    e[a].append((b,c))
    e[b].append((a,c))
q,k=map(int,input().split())
a=deque()
a.append((k,0))
while a:
    x,d=a.popleft()
    dist[x]=d
    for j,nc in e[x]:
        if dist[j]!=-1:
            continue
        else:
            a.append((j,d+nc))
ans=[]
for i in range(q):
    x,y=map(int,input().split())
    ans.append(dist[x]+dist[y])
print(*ans,sep="\n")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def print_ans(N, S):
    """Test Case
    >>> print_ans(4, "0224")
    3
    >>> print_ans(6, "123123")
    17
    """
    s = set()
    for i in range(N):
        for k in range(i+1,N):
            for l in range(k+1, N):
                s.add(S[i] + S[k] + S[l])
    print(len(s))



    
if __name__ == '__main__':
    N = int(input().rstrip())
    S = input().rstrip()
    print_ans(N, S)


### FIXED CODE ###

import sys
input = sys.stdin.readline
lists = ['{0:03d}'.format(i) for i in range(1000)]
import re
def check(target, a):
    ans = re.search(a, target)
    if ans == None:
        return None
    else:
        return target[ans.start()+1:]

def print_ans(N, S):
    """Test Case
    >>> print_ans(4, "0224")
    3
    >>> print_ans(6, "123123")
    17
    >>> print_ans(19, "3141592653589793238")
    329
    """
    # s = set()
    # for i in range(N):
    #     for k in range(i+1,N):
    #         for l in range(k+1, N):
    #             s.add(S[i] + S[k] + S[l])
    # print(len(s))
    ans = 0
    for a in lists:
        tmp = S
        for i in range(3):
            tmp = check(tmp, a[i])
            if tmp == None:
                break
        if tmp != None:
            ans += 1
    print(ans)


    # print(check('123','4'))


    
if __name__ == '__main__':
    N = int(input().rstrip())
    S = input().rstrip()
    print_ans(N, S)
### BUGGY CODE ###

s = input()
p = 2019
n = 0
ans = 0
mods = [0]*p
mods[0] = 1
for i, j in enumerate(reversed(s)):
  n = (n+int(j)*10**i)%p
  mods[n] += 1
for i in mods:
  ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

s = input()
p = 2019
n = 0
ans = 0
mods = [0]*p
mods[0] = 1
for i, j in enumerate(reversed(s)):
  n += int(j)*pow(10, i, p)
  n %= p
  mods[n] += 1
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

# coding:utf-8
# Doubly Linked List


def main():

    n = int(input())
    ans = ""
    dll = []
    for _ in range(n):
        operation = input().split()
        command = operation[0]
        if len(command) == 6:
            key = str(operation[1])
            if command == "insert":
                dll.insert(0, key)
            else:
                try:
                    dll.remove(key)
                except:
                    pass

        else:
            if command[6] == 'F':
                dll.pop(0)
            else:
                dll.pop(-1)

    print(' '.join(dll))

if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding:utf-8
# Doubly Linked List

from collections import deque

def main():

    n = int(input())
    dll = deque()

    for _ in range(n):
        operation = input().split(' ')
        if operation[0] in ["insert", "delete"]:
            key = operation[1]
            if operation[0] == "insert":
                dll.appendleft(key)
            else:
                try:
                    dll.remove(key)
                except:
                    pass

        else:
            if operation[0][6] == 'F':
                dll.popleft()

            else:
                dll.pop()

    print(' '.join(dll))

if __name__ == "__main__":
    main()
### BUGGY CODE ###

inf = float('inf')
# ベルマンフォード法
# 計算量O(VE) V:頂点数, E:辺の数
# [引数]   n:頂点数, edges:辺集合, start:始点, end:終点
# [返り値] dist:startからの最短距離, exists_negative_cycle: 負閉路が存在するかどうか
def bellmanford(n : int, edges : list, start : int, goal : int) -> (list, bool):
    dist = [inf] * n
    dist[start] = 0
    exist_negative_cycle = True

    # 負閉路を含まないとき、頂点数nなら更新は高々n-1回で済む
    for _ in range(N-1):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w


    # (1)グラフに負閉路が含まれるときの検出
    # N回目で更新があったとき、グラフは負閉路を含む
    # for v, nv, w in edges:
    #     if dist[nv] > dist[v] + w:
    #         is_cycle = False

    # (2)startとgoalのパスに負閉路が含まれるときの検出
    is_updated = [False] * n
    for _ in range(N):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                is_updated[nv] = True
            if is_updated[v] is True:
                is_updated[nv] = True

    exist_negative_cycle = is_updated[goal]

    return dist, exist_negative_cycle

N, M, P = map(int,input().split())
edges = []
for _ in range(M):
    A, B, C = map(int,input().split())
    A -= 1; B -= 1
    C = C - P
    edges.append((A, B, -C))

dist, exist_negative_cycle = bellmanford(N, edges, 0, N-1)

if exist_negative_cycle is True:
    ans = -1
else:
    ans = max(-dist[N-1], 0)

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**4)

inf = float('inf')

# 計算量O(VE) V:頂点数, E:辺の数
# True - >正常に更新, False -> startからendまでの経路において負閉路有り
def bellmanford(start, end):
    global dist
    dist = [inf] * N
    dist[start] = 0
    # 頂点数Nなら更新は高々N-1回で済む
    for _ in range(N-1):
        for v ,nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
    # 負閉路の検出部分
    # N回目で更新があった場合、負閉路を含む
    for v, nv, w in edges:
        if dist[nv] > dist[v] + w:
            return False
    return True

def dfs(v, ad):
    visited[v] = True
    for nv in ad[v]:
        if not visited[nv]:
            dfs(nv, ad)

N, M, P = map(int,input().split())
to = [[] for _ in range(N)]
fr = [[] for _ in range(N)]
edges = []
for _ in range(M):
    A, B, C = map(int,input().split())
    A -= 1
    B -= 1
    C -= P
    C *= -1
    to[A].append(B)
    fr[B].append(A)
    edges.append((A, B, C))

visited = [False] * N

dfs(0, to)
tmp = visited[:]
visited = [False] * N
dfs(N-1, fr)
visited = [a and b for a, b in zip(tmp, visited)]
edges = [(v, nv, w) for v, nv, w in edges if visited[v] and visited[nv]]

flag = bellmanford(0, N-1)
ans = max(-dist[N-1], 0) if flag else -1
print(ans)
### BUGGY CODE ###

n = int(input())
A = []
for i in range(n):
    k = int(input())
    if k in A:
        del A[A.index(k)]
    else:
        A.append(k)
print(len(A))

### FIXED CODE ###

n = int(input())
s = set()
for i in range(n):
    k = int(input())
    if k in s:
        s.remove(k)
    else:
        s.add(k)
print(len(s))