Harryxun/stf_run huggingface dataset:
n, MOD = int(input()), 10 ** 9 + 7

memo = [{} for _ in range(n+1)]
def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i], t[i-1] = t[i-1], t[i]
        if "".join(t).count("AGC") != 0:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in "AGCT":
        if ok(last3 + c):
            ret = (ret + dfs(cur+1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))

### FIXED CODE ###

n, MOD = int(input()), 10 ** 9 + 7

memo = [{} for _ in range(n+1)]
def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i], t[i-1] = t[i-1], t[i]
        if "".join(t).count("AGC") != 0:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == n:
        return 1
    ret = 0
    for c in "AGCT":
        if ok(last3 + c):
            ret = (ret + dfs(cur+1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))
,X=map(int,input().split())
a=[]
for i in range(0,K):
  a.append(X-i)
for j in range(1,K):
  a.append(X+j)
s=a.sort()
print(s)

### FIXED CODE ###

K,X=map(int,input().split())
for i in range(X-K+1,X+K):
  print(i)
N = int(input())
Xs = [list(map(int, input().split(" "))) for _ in range(N)]
"""
input = ["2 3 5","2 1 5","1 2 5","3 2 5"]
input = ["0 0 100", "1 1 98"]
input = ["99 1 191", "100 1 192", "99 0 192"]
Xs = [list(map(int, x.split(" "))) for x in input]
"""
Xs.sort(key=lambda x:x[2], reverse=True)


def solv(Xs):
    for x in range(101):
        for y in range(101):
            h= Xs[0][2]
            Cx = Xs[0][0]
            Cy = Xs[0][1]
            H = h + abs(x - Cx) + abs(y - Cy)
            for i in range(len(Xs)):
                if H - abs(x - Xs[i][0]) - abs(y - Xs[i][1]) != Xs[i][2]:
                    break
                if i == len(Xs)-1:
                    if H > 0:
                        return (x, y, H)


print("%d %d %d" % solv(Xs))


### FIXED CODE ###

N = int(input())
Xs = [list(map(int, input().split(" "))) for _ in range(N)]
"""
input = ["2 3 5","2 1 5","1 2 5","3 2 5"]
input = ["0 0 100", "1 1 98"]
input = ["99 1 191", "100 1 192", "99 0 192"]
Xs = [list(map(int, x.split(" "))) for x in input]
"""

Xs.sort(key=lambda x:x[2], reverse=True)


def solv(Xs):
    for x in range(101):
        for y in range(101):
            h= Xs[0][2]
            Cx = Xs[0][0]
            Cy = Xs[0][1]
            H = h + abs(x - Cx) + abs(y - Cy)
            for i in range(len(Xs)):
                h = max(H - abs(x - Xs[i][0]) - abs(y - Xs[i][1]), 0)
                if h != Xs[i][2]:
                    break
                if i == len(Xs)-1:
                    print("%d %d %d" % (x, y, H))
                    exit(0)


solv(Xs)
N, M = list(map(int, input().split(" ")))
list_a = list(map(int, input().split(" ")))

##最大公約数を求める

def gcd(a, b) :
  if(b==0) :
    return a
  else :
    return gcd(b, a%b)

##最小公倍数を求める
def lcm(a, b) :
  return a * b / gcd(a, b)
  
##複数個の整数の最小公倍数を求める
def lcm_multi(l) :
  res = lcm(l[0], l[1])
  for i in range(2, N) :
    res = lcm(l[i], res)
    
  return res

ans = 0
lcm_m = lcm_multi(list_a)
if(M-lcm_m/2 < 0) :
  print(0)
else :
  print(int((M-lcm_m/2) / lcm_m) + 1)

### FIXED CODE ###

N, M = list(map(int, input().split(" ")))
list_a = list(map(int, input().split(" ")))

##半公倍数が存在するかチェック
def check_exist(l) :
  if(len(l) == 1) :
    return True
  while(True) :
    flag = l[0] % 2
    for x in l[1:] :
      if(x % 2 != flag) :
        return False
    if(flag == 0) :
      l = list(map(lambda x: int(x/2), l))
    else :
      return True
    

##最大公約数を求める

def gcd(a, b) :
  if(b==0) :
    return a
  else :
    return gcd(b, a%b)
   
##最小公倍数を求める
def lcm(a, b) :
  cd = gcd(a, b)
  return (a / cd) * b
  
##複数個の整数の最小公倍数を求める
def lcm_multi(l) :
  cm = 1
  for x in l :
    cm = lcm(x, cm)
    if(cm > 4 * M) :
      print(0)
      exit()
    
  return cm

if(not(check_exist(list_a))) :
  print(0)
  exit()

## 1/2の公倍数
lcm_m = lcm_multi(list(map(lambda x: int(x/2), list_a)))

if(M-lcm_m < 0) :
  print(0)
else :
  print(int((M-lcm_m) / (2*lcm_m)) + 1)
import os, sys, re, math

N = int(input())

#memo = [0 for _ in range(int(2*1e5)+1)]
memo = [0 for _ in range(2*int(1e5)+100)]

for _ in range(N):
	A,B = [int(s) for s in input().split(' ')]
	memo[B] += A

s = 0
flg = True
for i in range(len(memo)):
	s += memo[i]
	if s > i:
		flg = False
		break
if flg:
	print('Yes')
else:
	print('No')


### FIXED CODE ###

import os, sys, re, math

N = int(input())

#memo = [0 for _ in range(int(2*1e5)+1)]
memo = {}

for _ in range(N):
	A,B = [int(s) for s in input().split(' ')]
	if B in memo:
		memo[B] += A
	else:
		memo[B] = A

s = 0
flg = True
key = list(memo.keys())
key = sorted(key)
for i in range(len(key)):
	s += memo[key[i]]
	if s > key[i]:
		flg = False
		break
if flg:
	print('Yes')
else:
	print('No')
import sys
s = input()
t = input()
table = [[len(s) for i in range(len(s))] for j in range(26)]

for i in range(len(s)):
  table[ord(s[i])-97][i] = 0
for i in range(26):
  if chr(97+1)
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])

for letter in t:
  if s.find(letter) == -1:
    print(-1)
    sys.exit()
    
place = 0
ans = 0
for i in range(len(t)):
  letter = t[i]
  move = table[ord(t[i])-97][place]
  ans += move + 1
  place = (place + move+1)%len(s)
print(ans)

### FIXED CODE ###

import sys
s = input()
t = input()
table = [[len(s) for i in range(len(s))] for j in range(26)]
sset = set(s)
tset = set(t)
for i in range(len(s)):
  table[ord(s[i])-97][i] = 0
for letter in sset:
  i = ord(letter) - 97
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])
  for j in range(len(s)):
    if table[i][len(s)-j-2] < len(s): break
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])

if tset - sset:
  print(-1)
  sys.exit()
    
place = 0
ans = 0
for i in range(len(t)):
  letter = t[i]
  move = table[ord(t[i])-97][place]
  ans += move + 1
  place = (place + move+1)%len(s)
print(ans)
from math import sqrt
n=int(input())
for i in range(int(sqrt(n)),0,-1):
  if n%i==0:
    j=n//i
    pirnt(i+j-2)
    break

### FIXED CODE ###

from math import sqrt

N = int(input())
for i in range(int(sqrt(N)), 0, -1):
    if N % i == 0:
        j = N // i
        print(i + j - 2)
        break
h, w = map(int, input().split())
long = max(h, w)
short = min(h, w)
if h%3==0 or w%3==0:
    print(0)
else:
    if long%3==1:
        s_max = long//3*short
        s_min = (long-long//3)*(short//2)
    elif long%3==2:
        s_max = (long//3+1)*short
        s_min = (long-(long//3+1))*(short//2)
print(abs(s_max-s_min))

### FIXED CODE ###

def f(x,y,z):
    return max(x,y,z)-min(x,y,z)

h, w = map(int, input().split())
l = []
ans1, ans2 = h*w, h*w
for i in range(1,h//2+1):
        s1 = i*w
        s2 = w*((h-i)//2)
        s3 = h*w-s1-s2
        s4 = (h-i)*(w//2)
        s5 = h*w-s1-s4
        ans1 = min(ans1, f(s1,s2,s3),f(s1,s4,s5))

for i in range(1,w//2+1):
        s1 = i*h
        s2 = h*((w-i)//2)
        s3 = h*w-s1-s2
        s4 = (w-i)*(h//2)
        s5 = h*w-s1-s4
        ans2 = min(ans2, f(s1,s2,s3),f(s1,s4,s5))
print(min(ans1,ans2))
a,b,c=map(int,input().split());print(min[a*b,c])

### FIXED CODE ###

a,b,c=map(int,input().split());print(min([a*b,c]))
a = list(map(int, input().split()))
if a[0] >= a[1]:
    b = a[0]
    c = a[1]
else:
    b = a[1]
    c = a[0]

s = int(a[2]/b)+1

print(s)

### FIXED CODE ###

h = int(input())
w = int(input())
n = int(input())
        
if h >= w:
  if n%h == 0:
    s = int(n/h)
  else:
    s = int(n/h)+1
    
else:
  if n%w == 0:
    s = int(n/w)
  else:
    s = int(n/w)+1

print(s)
# -*- coding: utf-8 -*-
# 整数の入力
a = int(raw_input())
print str(48-a)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
a = int(raw_input())
print str(48-a)
S=str(input())
L=[]
for S in range(4):
  L.append(S)
L.sort()

print('Yes' if L[0]==S[1] and S[2]==S[3] else 'No')

### FIXED CODE ###

S=str(input())
a=0
for i in S:
  if S.count(i)==2:
    a+=1
    
print('Yes' if a==4 else 'No')
import math
N,K=map(int,input().split())
pro=0
if N==1 and K==1:
    print(1)
elif N>=K:
    pro+=(N-K)/N
    for k in range(1, K):
        r = math.ceil(math.log2(K / k))
        pro += 0.5**r / N
        print(pro)

else:
    for k in range(1, N+1):
        r = math.ceil(math.log2(K / k))
        pro += 0.5**r / N
        print(pro)



### FIXED CODE ###

import math
N,K=map(int,input().split())
pro=0
if N==1 and K==1:
    print(1)
elif N>=K:
    pro+=(N-K+1)/N
    for k in range(1, K):
        r = math.ceil(math.log(K / k,2))
        pro += 0.5**r / N
    print(pro)

else:
    for k in range(1, N+1):
        r = math.ceil(math.log(K / k,2))
        pro += 0.5**r / N
    print(pro)
from collections import Counter
n = int(input())
v = list(map(int,input().split()))
a = Counter(v[0::2]).most_common()
b = Counter(v[1::2]).most_common()
a.append([0,0])
b.append([0,0])

if a[0][0] != b[0][0]:
  print(n-(a[0][1]+b[0][1]))
else:
  print(min(n-(a[1][1]+b[0][1]),n-(a[0][1]+b[1][1]))
         

### FIXED CODE ###

from collections import Counter
n = int(input())
v = list(map(int,input().split()))
a = Counter(v[0::2]).most_common()
b = Counter(v[1::2]).most_common()
a.append([0,0])
b.append([0,0])

if a[0][0] != b[0][0]:
  print(n-(a[0][1]+b[0][1]))
else:
  print(min(n-(a[1][1]+b[0][1]),n-(a[0][1]+b[1][1])))
L,N = map(int,input().split())
S = []
for _ in range(N):
    S.append(str(input()))
S.sort()
print(''.join(S))

### FIXED CODE ###

N,L = map(int,input().split())
list1 = []
for l in range(N):
    list1.append(str(input()))
list1.sort()
print(''.join(list1))
N = int(input())
ans = []
for i in range(N):
    A = int(input())
    if A in ans:
        ans.append(A)
    else:
        ans.remove(A)
print(len(ans))

### FIXED CODE ###

N = int(input())
num = {}
for i in range(N):
    A = int(input())
    if A in num.keys():
        num[A] += 1
    else:
        num[A] = 1
ans = 0
for i, j in num.items():
    if j%2 == 1:
        ans += 1
print(ans)
N=int(input())
S={}
cnt=0
for i in range(N):
    Z=sorted(list(input()))
    K="".join(Z)
    if K in S:
        S[K]+=1
    else:
        S[K]=1
cnt=0
for i in S.values():
    mul=1
    if i!=0 and i!=1:
        for t in range(i,1,-1):
            mul*=t
        v=mul/2
        cnt+=v
print(int(cnt))    

### FIXED CODE ###

N=int(input())
S={}
cnt=0
for i in range(N):
    Z=sorted(list(input()))
    K="".join(Z)
    if K in S:
        S[K]+=1
    else:
        S[K]=1
for T in S.values():
    mul=1
    v=1
    if T>1:
        mul=(T*(T-1))//2
        cnt+=mul
    else:
        continue
print(int(cnt))
N = int(input())
S = input()
assert len(S) == N
count = 0
for i in range(0, len(S)-2):
  for j in range(i+1, len(S)-1):
    if S[i] == S[j]:
      continue
    SiSj = Si + Sj
    if 'R' not in SiSj:
      Sk = 'R'
    elif 'G' not in SiSj:
      Sk = 'G'
    else:
      Sk = 'B'
    for k in range(j+1, len(S)):
      # RGBのどれかになるはず
      if Sk == S[k]:
        if j - i != k - j:
          count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = input()
assert len(S) == N
count = 0

# j-i = k-jを探す
for i in range(0, len(S)-2):
  for j in range(i+1, len(S)-1):
    k = j + (j - i)
    if k < len(S):
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        count += 1
numR = 0
numG = 0
numB = 0
for s in S:
  if s == 'R':
    numR += 1
  elif s == 'G':
    numG += 1
  else:
    numB += 1

print(numR * numG * numB - count)
from collections import Counter
N=int(input())
listS=[]
for i in range(N):
  S=input()
  listS+=[S]
listS=Counter(listS).most_common()
ans=[]
MAX=listS[0][1]
for i in range(N):
  if listS[i][1]==MAX:
    ans+=[listS[i][0]]
  else:
    break   
ans.sort()
for i in ans:
  print(i)

### FIXED CODE ###

N=int(input())
listS=[]
for i in range(N):
  S=input()
  listS+=[S]
listS.sort()
counter=[]
count=1
for i in range(N-1):
  if listS[i]==listS[i+1]:
    count+=1
  else:
    counter+=[count]
    count=1
    
counter+=[count]    
MAX=max(counter)
count=1

for i in range(N-1):
  if listS[i]==listS[i+1]:
    count+=1
  else:
    count=1
  if count==MAX:
    print(listS[i])
    
if MAX==1:
  print(listS[-1])
import bisect

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

Edge = [[] for _ in range(N)]
for _ in range(N-1):
    u,v = map(int,input().split())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)

visited = [False]*N
visited[0] = True
answer = [1]*N

def dfs(v, dp):
    for nv in Edge[v]:
        if visited[nv]:
            continue
        
        visited[nv] = True
        if len(dp)==0 or A[nv]>dp[-1]:
            dp.append(A[nv])
            answer[nv] = len(dp)
            dfs(nv, dp)
            dp.pop()
        else:
            idx = bisect.bisect_left(dp, A[nv])
            temp = dp[idx]
            dp[idx] = A[nv]
            answer[nv] = len(dp)
            dfs(nv, dp)
            dp[idx] = temp
        
    return 

dfs(0, [A[0]])
answer[0] = 1
for a in answer:
    print(a)




### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(10**9)

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

Edge = [[] for _ in range(N)]
for _ in range(N-1):
    u,v = map(int,input().split())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)

visited = [False]*N
visited[0] = True
answer = [1]*N

def dfs(v, dp):
    for nv in Edge[v]:
        if visited[nv]:
            continue
        
        visited[nv] = True
        if len(dp)==0 or A[nv]>dp[-1]:
            dp.append(A[nv])
            answer[nv] = len(dp)
            dfs(nv, dp)
            dp.pop()
        else:
            idx = bisect.bisect_left(dp, A[nv])
            temp = dp[idx]
            dp[idx] = A[nv]
            answer[nv] = len(dp)
            dfs(nv, dp)
            dp[idx] = temp
        
    return 

dfs(0, [A[0]])
answer[0] = 1
for a in answer:
    print(a)
from itertools import combinations

N, K = map(int, input().split())
points = []
for i in range(N):
    points.append(list(map(int, input().split())))

points.sort(key=lambda p:p[0])


min_area = 10**20
for k in range(K, N+1):
    for l in range(0, N-k+1):
        points_tmp = points[l:l+k-1]
        points_tmp.sort(key=lambda p:p[1])
        for m in range(0, N-K+1):
            points_selected = points_tmp[m, m+K-1]
            ymin = points_selected[0][1]
            ymax = points_selected[-1][1]
            points_selected.sort(key=lambda p:p[0])
            xmin = points_selected[0][0]
            xmax = points_selected[-1][0]
            area = (xmax-xmin) * (ymax-ymin)
            min_area = min(area, min_area)

print(min_area)


### FIXED CODE ###

from itertools import combinations

N, K = map(int, input().split())
points = []
for i in range(N):
    points.append(list(map(int, input().split())))

xl = list(map(lambda p: p[0],
              points))
yl = list(map(lambda p: p[1],
              points))

def contained(point, xmin, xmax, ymin, ymax):
    return (xmin <= point[0] <= xmax) and (ymin <= point[1] <= ymax)

def count_contained(xmin, xmax, ymin, ymax):
    count = 0
    for point in points:
        if contained(point, xmin, xmax, ymin, ymax):
            count += 1
    return count

min_area = 10**20
for xs in combinations(xl, 2):
    xmin = min(xs)
    xmax = max(xs)
    for ys in combinations(yl, 2):
        ymin = min(ys)
        ymax = max(ys)
        if count_contained(xmin, xmax, ymin, ymax) >= K:
            area = (xmax-xmin) * (ymax-ymin)
            min_area = min(area, min_area)
print(min_area)
c,d=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
e=0;i=0
while i<d-e:
    p=i;q=0
    for j in range(c):
        if a[j]==b[p]:q+=1;p+=1
    e=max(e,q)
    i+=1
print(e)

### FIXED CODE ###

s=list(map(int,input().split()))
if len(s)>1:c=s[0];d=s[1]
else:c=s[0];d=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
e=0;i=0
while i<d-e:
    p=i;q=0
    for j in range(c):
        if a[j]==b[p]:q+=1;p+=1
    e=max(e,q)
    i+=1
print(e)
from collections import deque
N = int(input())
A = deque(sorted([int(input()) for _ in range(N)]))
que = deque([])
que.append(A.popleft())
turn = 1
while A:
    if turn == 1:
        que.appendleft(A.pop())
        if A:
            a = A.pop()
            if abs(a-q[0])<=abs(a-q[-1]):
                que.append(a)
            else:
                que.appendleft(a)
    else:
        que.appendleft(A.popleft())
        if A:
            a = A.pop()
            if abs(a-q[0])<=abs(a-q[-1]):
                que.append(a)
            else:
                que.appendleft(a)
    turn = 1-turn
cnt = 0
for i in range(1,N):
    cnt += abs(que[i]-que[i-1])
print(cnt)

### FIXED CODE ###

from collections import deque
N = int(input())
A = deque(sorted([int(input()) for _ in range(N)]))
B = deque([])
B.append(A.popleft())
cnt = 0
while A:
    a0 = A[0]
    a1 = A[-1]
    b0 = B[0]
    b1 = B[-1]
    c00 = abs(a0-b0)
    c01 = abs(a0-b1)
    c10 = abs(a1-b0)
    c11 = abs(a1-b1)
    cmax = max(c00,c01,c10,c11)
    if cmax == c00:
        B.appendleft(A.popleft())
    elif cmax == c01:
        B.append(A.popleft())
    elif cmax == c10:
        B.appendleft(A.pop())
    else:
        B.append(A.pop())
    cnt += cmax
print(cnt)
a =  float(raw_input())
c = float(raw_input())
print (2*c-a)

### FIXED CODE ###

a =  float(raw_input())
c = float(raw_input())
print int(2*c-a)
import itertools

n = int(input())
a = sorted([int(input()) for i in range(n)])[:4]
b = []
for c,d in intertools.permutations(a,2):
    b += [c * 10**len(str(d)) + d]
print(sorted(b)[2])


### FIXED CODE ###

import itertools

n = int(input())
a = sorted([int(input()) for i in range(n)])[:4]
b = []
for c,d in itertools.permutations(a,2):
    b += [c * 10**len(str(d)) + d]
print(sorted(b)[2])
import numpy as np

N = int(input())
A = np.array(input().split(), np.float32)
B = np.arange(1, N + 1)
X = A[None, :] + A[:, None]
Y = np.abs(B[None, :] - B[:, None])
print(np.count_nonzero(X == Y) // 2)


### FIXED CODE ###

from _collections import defaultdict
import sys

read = sys.stdin.buffer.read
N = int(input())
A = [int(i) for i in input().split()]
D = defaultdict(int)

for i, a in enumerate(A, 1):
    D[i - a] += 1

ans = 0
for i, a in enumerate(A, 1):
    ans += D[i + a]
print(ans)
s = input()

count = 0

for i in range(s):
  if i == "o":
    count +=
    
print(700 + count * 100)


### FIXED CODE ###

s = input()

count = 700

for i in s:
  if i == "o":
    count += 100
    
print(count)
import numpy as np

import sys
sys.setrecursionlimit(1000000)

c = [list(map(int,input().split())) for _ in range(5)]

last = 10

for i in range(5):
    if c[i][0] % 10 ==  0:
        continue
    else:
        if last > c[i][0] % 10:
            last = c[i][0] % 10
            idx = i
    
ans = 0


for i in range(5):
    if i == idx:
        ans = ans + c[i][0]
    else:
        if c[i][0] % 10 == 0:
            ans = ans + c[i][0]
        else:
            ans= ans + ( c[i][0] // 10 + 1 ) * 10


print(ans)

### FIXED CODE ###

c = [int(input()) for _ in range(5)]

last = 10

idx = 0

for i in range(5):
    if c[i] % 10 ==  0:
        continue
    else:
        if last > c[i] % 10:
            last = c[i] % 10
            idx = i
    
ans = 0


for i in range(5):
    if i == idx:
        ans = ans + c[i]
    else:
        if c[i] % 10 == 0:
            ans = ans + c[i]
        else:
            ans= ans + ( c[i] // 10 + 1 ) * 10


print(ans)
N,M = list(map(int, input().split()))
AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))
AB = sorted(AB)

n = 0
result = 0

while True:
    if AB[n][1] <= M:
        result += AB[n][0] * AB[n][1]
        M -= AB[n][1]
        n += 1
    else:
        result += AB[n][0] * M
        break

print(result)

### FIXED CODE ###

N,M = list(map(int, input().split()))
AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))
AB = sorted(AB)

n = 0
result = 0

while M > 0:
    if AB[n][1] <= M:
        result += AB[n][0] * AB[n][1]
        M -= AB[n][1]
        n += 1
    else:
        result += AB[n][0] * M
        break

print(result)
n,m,r=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]

g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

dist=[-10**15 for _ in [0]*n]
dist[0]=0
a,b=-10**15,-10**15

for _ in range(n):
    for p in range(n):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j)
    a,b=b,dist[n-1]

if a==b:
    ans=0
    loop=set()
    d=[-10**15 for _ in [0]*n]
    d[0]=0
    q=[[0,1]]
    s=set()
    l=[]
    cnt=0
    while q:
        cnt+=1
        qq=[]
        for q_item in q:
            item,depth=q_item
            if depth<=len(s):
                for _ in range(len(s)-depth+1):
                    rmv=l.pop()
                    s.remove(rmv)
            l.append(item)
            s.add(item)
            for i,dist in g[item]:
                if d[i]<d[item]+dist:
                    if i in s:
                        loop.add(i)
                        continue
                    d[i]=d[item]+dist
                    qq.append([i,depth+1])
          
        c=[False for _ in [0]*n]
        for x in loop:
            if c[x]==True:
                continue
            qqq=[x]
            c[x]=True
            while qqq:
                item=qqq.pop()
                for i,j in g[item]:
                    if c[i]==False:
                        c[i]=True
                        qq.append(i)
        ans=max(ans,d[n-1]-cnt*r)
        q=qq
    print(ans)
else:
    print(-1)

### FIXED CODE ###

#入力
n,m,r=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
#グラフ
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]
#逆辺
g2=[[] for _ in [0]*n]
[g2[b-1].append([a-1,c]) for a,b,c in abc]

#ベルマンフォード
dist=[-10**15 for _ in [0]*n]
dist[0]=0
a,b=-10**15,-10**15

for k in range(n):
    for p in range(n):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j-r)
    if k==n-2:
        d1=[t for t in dist]
    if k==n-1:
        d2=[t for t in dist]
    
#負の経路上の頂点の一覧
loop=set()
for i in range(n):
    if d1[i]!=d2[i]:
        loop.add(i)    
ans=max(d2[n-1],0)

#1からの到達可能地点
q=[0]
memo=[True for _ in range(n)]
memo[0]=False
while q:
    qq=q.pop()
    for i,j in g[qq]:
        if memo[i]:
            q.append(i)
            memo[i]=False
            
#nからの逆辺による到達可能地点
q=[n-1]
memo2=[True for _ in range(n)]
memo2[n-1]=False
while q:
    qq=q.pop()
    for i,j in g2[qq]:
        if memo2[i]:
            q.append(i)
            memo2[i]=False
            
#1からでもnからでも行ける点でかつ負の閉路に入っているものがあるときは-1
for i in loop:
    if memo[i]==False and memo2[i]==False:
        ans=-1
        
print(ans)