Harryxun/stf_run huggingface dataset:
#N, M, X = [int(n) for n in input().split()]

#CA = [list(map(int, input().split())) for n in range(N)]

#print(N,M,X)
#print(CA)

min_cost = 12*10**5


def dfs(CA, cost, skills, cur, used, min_cost):
  #Pdb().set_trace()
  #print(cur)
  skills = [skills[i] + n for i, n in enumerate(CA[cur][1:])]
  used += [cur]
  cost += CA[cur][0]
  
  if all([s >= X for s in skills]):
  	return cost
  else:
    candidates = [n for n in range(N) if n not in used]
    prev_used = used
    prev_skills = skills
    prev_cost = cost
    for i in candidates:
        min_cost = min(min_cost, dfs(CA, prev_cost, prev_skills, i, prev_used, min_cost))
  return min_cost
       

for i in range(N):
  Pdb().set_trace()
  used = []
  cost = 0
  skills = [0] * M
  min_cost = min(min_cost, dfs(CA, cost, skills, i, used, min_cost)) 

print(min_cost)

### FIXED CODE ###

N, M, X = [int(n) for n in input().split()]

CA = [list(map(int, input().split())) for n in range(N)]

ans = 10**10

for i in range(2**N):
  cost = 0
  skills = [0] * M
  for j in range(N):
    if ((i >> j) & 1):
      #print(i, j)
      for k in range(M):
        skills[k] += CA[j][1+k]
      cost += CA[j][0]
  #print("skills", skills)
  if all([n >= X for n in skills]):
  	ans = min(ans, cost)
  #print("ans", ans)
if ans == 10**10:
  print(-1)
else:
  print(ans)
n, k = map(int, input().split())
s = list(input())

s_c = []

left = 0
right = 0
for i in range(n - 1):
    if s[i] == s[i + 1]:
        right = i + 1
    else:
        s_c.append(''.join(s[left:right + 1]))
        i += 1
        left = i
        right = i
s_c.append(''.join(s[left:right + 1]))

cc = 'R'
if s_c[1][0] == 'R':
    cc = 'L'

s_c_len = len(s_c)
for i in range(k):
    if (2 * i + 1) > s_c_len - 1:
        break
    s_c[2 * i + 1] = cc * len(s_c[2 * i + 1])

ans_s = ''.join(s_c)
ans = 0
for i in range(n):
    if ans_s[i] == 'R' and i != n - 1 and ans_s[i + 1] == 'R':
        ans += 1
    elif ans_s[i] == 'L' and i != 0 and ans_s[i - 1] == 'L':
        ans += 1
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
s = list(input())

s_c = []

left = 0
right = 0
for i in range(n - 1):
    if s[i] == s[i + 1]:
        right = i + 1
    else:
        s_c.append(''.join(s[left:right + 1]))
        i += 1
        left = i
        right = i
s_c.append(''.join(s[left:right + 1]))

s_c_len = len(s_c)
cc = 'R'
if s_c_len > 1 and s_c[1][0] == 'R':
    cc = 'L'

for i in range(k):
    if (2 * i + 1) > s_c_len - 1:
        break
    s_c[2 * i + 1] = cc * len(s_c[2 * i + 1])

ans_s = ''.join(s_c)
ans = 0
for i in range(n):
    if ans_s[i] == 'R' and i != n - 1 and ans_s[i + 1] == 'R':
        ans += 1
    elif ans_s[i] == 'L' and i != 0 and ans_s[i - 1] == 'L':
        ans += 1
print(ans)
Z = input().split()
A = int(Z[0])
B = Z[1].split('.')
B = int(B[0] + B[1])
#print(A*B)
a = str(A*B)[:-2]
a = int(a)
print(a)


### FIXED CODE ###

Z = input().split()
A = int(Z[0])
B = Z[1].split('.')
B = int(B[0] + B[1])
#print(A*B)
if len(str(A*B)) <= 2:
  a = 0
else:
  a = str(A*B)[:-2]
  a = int(a)
print(a)
k, s = list(map(int, input().split()))
num = 0

for x in range(k+1):
  for y in range(k+1):
    if s-k <= x+y <= s:
      num += 1

print(num)


### FIXED CODE ###

s = input()
print(s.replace(',', ' '))
N , T = map(int, input().split())
mini = T
for i in range(N):
    c , t = input().split()
for i in  range(N):
    if int(t[i])<mini:
        mini = int(t[i])
if mini<T:
    print(c[i])
else:
    print("TLE")

### FIXED CODE ###

N,T=map(int,input().split())
c=[]
mn=1001
for i in range(N):
    cost,time=map(int,input().split())
    if time<=T:
        c.append(cost)
for i in c:
    if i<=mn:
        mn=i
if len(c)==0:
    print('TLE')
else:
    print(mn)
import itertools

def solve():
    cache = {}
    def loop(i, w):
        if (i, w) in cache:
            return cache[i, w]
        if i == N:
            return (0, 0)
        cache[i, w] = loop(i + 1, w)
        if v[i][1] <= w:
            t = loop(i + 1, w - v[i][1])
            cache[i, w] = max(cache[i, w], (t[0] + v[i][0], t[1] + v[i][1]), key=lambda u: u[0])
        return cache[i, w]
    return loop(0, W)

for dn in itertools.count(1):
    W = int(input())
    if W == 0: break
    N = int(input())
    v = [tuple(map(int, input().split(','))) for _ in range(N)]
    optim = solve()
    print("Case %d:\n%d\n%d" % (dn, optim[0], optim[1]))

### FIXED CODE ###

import itertools

for dn in itertools.count(1):
    W = int(input())
    if W == 0: break
    N = int(input())
    d = [tuple(map(int, input().split(','))) for _ in range(N)]

    v = [0 for _ in range(W + 1)]
    for i in range(N):
        for j in range(W, d[i][1] - 1, -1):
            v[j] = max(v[j], v[j - d[i][1]] + d[i][0])
    print("Case %d:\n%d\n%d" % (dn, max(v), v.index(max(v))))
n, k = map(int, input().split())
s = str(input())

if s[k-1] == 'A':
    s[k-1] = 'a'

elif s[k-1] == 'B':
    s[k-1] = 'b'

elif s[k-1] == 'C':
    s[k-1] = 'c'

### FIXED CODE ###

n, k = map(int, input().split())
s = str(input())

if s[k-1] == 'A':
    print(s[:k-1] + 'a' + s[k:])

elif s[k-1] == 'B':
    print(s[:k-1] + 'b' + s[k:])

else:
    print(s[:k-1] + 'c' + s[k:])
#!/usr/bin/env python3]
import sys
sys.setrecursionlimit(2000)

N = int(input())
syogen = []
for i in range(N):
    N_a = int(input())
    syogen_a = []
    for _ in range(N_a):
        x, y = input().split()
        syogen_a.append([int(x) - 1, int(y)])
    syogen.append(syogen_a)


def syojiki(i):
    for x, y in syogen[i]:
        if y == 1:
            syojiki_list.append(x)
            if len(syojiki_list) >= N:
                return
            syojiki(x)


def check_syojiki(syojikitati):
    d = {}
    for s in range(N):
        if not (s in syojikitati):
            d[s] = 0

    for s in syojikitati:
        d[s] = 1
        for x, y in syogen[s]:
            if d[x] != y:
                return False
            else:
                d[x] = y
    return True


max_syojiki = 0

for i in range(2 ** N):
    d = {}
    syojiki_list = []
    for j in range(N):
        if (i >> j) & 1:
            syojiki_list.append(j)
            syojiki(j)
    syojiki_list = list(set(syojiki_list))
    if check_syojiki(syojiki_list):
        max_syojiki = max(max_syojiki, len(syojiki_list))

print(max_syojiki)


### FIXED CODE ###

#!/usr/bin/env python3]
import sys
sys.setrecursionlimit(2000)

N = int(input())
syogen = []
for i in range(N):
    N_a = int(input())
    syogen_a = []
    for _ in range(N_a):
        x, y = input().split()
        syogen_a.append([int(x) - 1, int(y)])
    syogen.append(syogen_a)


def syojiki(i):
    for x, y in syogen[i]:
        if y == 1:
            syojiki_list.append(x)
            if len(syojiki_list) >= N:
                return
            syojiki(x)


def check_syojiki(syojikitati):
    d = {}
    for s in range(N):
        if s in syojikitati:
            d[s] = 1
        else:
            d[s] = 0

    for s in syojikitati:
        d[s] = 1
        for x, y in syogen[s]:
            if d[x] != y:
                return False
    return True


max_syojiki = 0

for i in range(2 ** N):
    d = {}
    syojiki_list = []
    for j in range(N):
        if (i >> j) & 1:
            syojiki_list.append(j)
            syojiki(j)
    syojiki_list = list(set(syojiki_list))
    if check_syojiki(syojiki_list):
        max_syojiki = max(max_syojiki, len(syojiki_list))

print(max_syojiki)
ef cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
N = 10**4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


N, K = map(int, input().split())
R = N-K

for i in range(1, K+1):
    if i > R+1:
        print(0)
    else:
        ans = cmb(R+1, i, mod) * cmb(K-1, i-1, mod) % mod
        print(ans)


### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
N = 10**4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


N, K = map(int, input().split())
R = N-K

for i in range(1, K+1):
    if i > R+1:
        print(0)
    else:
        ans = cmb(R+1, i, mod) * cmb(K-1, i-1, mod) % mod
        print(ans)
"""
author : halo2halo
date : 23, Jan, 2020
"""

import sys

# import itertools
# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

S = readline().decode('utf8').rstrip()
lis = list(S)
# print(lis)
print(lis.index('C'))
print(len(lis))
if lis[0] == 'A' and 2 <= lis.index('C') <= len(lis) - 2:
    st = ''.join(lis[1:lis.index('C')] + lis[lis.index('C') + 1:])
    # print(st)
    if st.lower():
        print('AC')
    else:
        print('WA')

else:
    print('WA')


### FIXED CODE ###

"""
author : halo2halo
date : 23, Jan, 2020
"""

import sys

# import itertools
# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

S = list(readline().decode('utf8').rstrip())
bl = S[0] == 'A'
bl &= ('C' in S[2:-1])

if bl:
    S.remove('A')
    S.remove('C')

bl &= all('a' <= x <= 'z' for x in S)

print('AC' if bl else 'WA')
import math
b = list(map(int,input().split()))
ans=0
check=0
A=0
C=b[1]
max = math.floor(b[2]/b[1])
if max == 0:
    if b[1]-1>0:
        check = math.floor((b[0]*(b[1]-1))/b[1]) - b[0]*math.floor((b[1]-1)/b[1])
        if check > ans:
            ans=check
else:
    for i in range(max+1):
        A=b[1]-1
        if A>0:
            check = math.floor((b[0]*A)/C) - b[0]*math.floor(A/C)
            if check > ans:
                ans=check
        b[1]+=b[1]
print(ans)

### FIXED CODE ###

import math
b = list(map(int,input().split()))
ans=0
check=0
if b[2]>b[1]-1:
    check = math.floor((b[0]*(b[1]-1))/b[1]) - b[0]*math.floor((b[1]-1)/b[1])
else:
    check = math.floor((b[0]*b[2])/b[1]) - b[0]*math.floor(b[2]/b[1])
if check>ans:
    ans=check
print(ans)
n = int(input())
x = list(map(int, input().split()))
mid = int(sum(x)/n)
ans = []
total = 0
for p in range(x[0], x[n-1] + 1):
    for i in range(n):
        total += (x[i] - p)**2
    ans.append(total)
    total = 0
print(min(ans))

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
ans = []
total = 0
for p in range(min(x), max(x) + 1):
    for i in range(n):
        total += (x[i] - p)**2
    ans.append(total)
    total = 0
print(min(ans))
dict={"A":"T","T":"A","G":"C","C":"G"}
print(dict(input()))


### FIXED CODE ###

dict={"A":"T","T":"A","G":"C","C":"G"}
print(dict[input()])
N, Q = map(int, input().split())
s = input()
T = []
D = []
for _ in range(Q):
	t, d = input().split()
	T.append(t)
	D.append(d)


ans = 0
left = 0
right = N-1
for i in range(Q-1,-1,-1):
	if D[i] == 'R':
		if T[i] == s[right]:
			right -= 1
		if left > 0 and s[left-1]==T[i]:
			left -= 1

	else:
		if T[i] == s[left]:
			left += 1
		if right < N-1 and s[right+1]==T[i]:
			right += 1
	# print(s[left:right+1])
print(right-left+1)


### FIXED CODE ###

N, Q = map(int, input().split())
s = input()
T = []
D = []
for _ in range(Q):
	t, d = input().split()
	T.append(t)
	D.append(d)


ans = 0
left = 0
right = N-1
for i in range(Q-1,-1,-1):
	if D[i] == 'R':
		if T[i] == s[right]:
			right -= 1
			if right == 0:
				print(0)
				exit()
		if left > 0 and s[left-1]==T[i]:
			left -= 1

	else:
		if T[i] == s[left]:
			left += 1
			if left == N-1:
				print(0)
				exit()
		if right < N-1 and s[right+1]==T[i]:
			right += 1
	# print(s[left:right+1])
print(max(0,right-left+1))
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(len(a)):
    b.append((a[i]+1)/2)
for i in range(len(a)-k+1):
    sum=0
    for j in range(i,i+k):
        sum+=b[j]
    if max<=sum:
        max=sum
print(max)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans='YES'
for i in range(1,len(a)):
    if a[i-1]==a[i]:
        ans="NO"
        break

print(ans)
def a(t,x,y):
    n=abs(x)+abs(y)
    if (t-n)%2==0 and t-n>=0 :
        return 1
    else :
        return 0
N=int(input())
result=1
tn,xn,yn=0,0,0
for i in range(N):
    t,x,y=map(int,input().split())
    tn=t-tn
    xn=x-xn
    yn=y-yn
    result*=a(tn,xn,yn)
    #print (result)
if result==1:
    print ('Yes')
else:
    print ('No')

### FIXED CODE ###

a,b=map(int,input().split())
if a*b%2 :
    print('Odd')
else:
    print('Even')
n=int(input())
l=list(map(int,input().split()))
if min(l)== 0:
    print(0)
else:    
    s=1
    for x in l:
        s *= x
        if s>1000000000000000000:
            s=1
            break
            
print(s)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
if min(l)== 0:
    print(0)
else:    
    s=1
    for x in l:
        s *= x
        if s>10**18:
            s=-1
            break
    print(s)
a,b,c,d=map(int.input().split())
print(min(b,d)-(max(a,c))

### FIXED CODE ###

a,b,c,d=map(int,input().split())
if(b<=c or d<=a):
  print(0)
else:
  print(abs(min(b,d)-max(a,c)))
N = str(input())

if "7" in N:
  print("Yes")
  
else:
  print("No")ｃ

### FIXED CODE ###

N = str(input())
if "7" in N:
  print("Yes")
else:
  print("No")
n=int(input())
x=list(map(int,input().split()))
l=[]
while len(x):
    for i,a in enumerate(x):
        if a==i+1:
            index=i
    l.append(x.pop(index))
for i in reversed(l):
    print(i)

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
l=[]
while len(x):
    index=-1
    for i,a in enumerate(x):
        if a==i+1:
            index=i
    if index == -1:
        print(-1)
        break
    l.append(x.pop(index))
else:
    for i in reversed(l):
        print(i)
n, a, b = map(int, input().split())

ans = 0
for num in range(n):
  num += 1
  num_0 = num
  place_of_1000 = num//1000
  num -= 1000*place_of_1000
  place_of_100 = num//100
  num -= 100*place_of_100
  place_of_10 = num//10
  num -= 10*place_of_10
  
  tmp = place_pf_10000 + place_of_1000 + place_of_100 + place_of_10 + num
  if a<=tmp and tmp<=b:
    ans += num_0
    
print(ans)

### FIXED CODE ###

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

total = 0

for n in range(1,N+1):
    sum = 0
    q = n
    while q != 0:
        sum += (q%10)
        q = q//10
    if (A<=sum) and (sum<=B):
        total += n

print(total)
x=int(input):
print(x**3)

### FIXED CODE ###

x = int(input())
print(x**3)
A,B = map(int,input().split())
X = A + B
Y = A - B
Z = A * B
  if X >= Y and X >= Z :
     print(X)
elif Y >= Z and Y >= X :
     print(Y)
elif Z >= X and Z >= Y :
     print(Z)

### FIXED CODE ###

A,B = map(int,input().split())
X = A + B
Y = A - B
Z = A * B
if X >= Y and X >= Z:
     print(X)
elif Y >= Z and Y >= X:
     print(Y)
elif Z >= X and Z >= Y:
     print(Z)
N,M = map(int,input().split())
ls = [0 for _ in range(N)]
flg = 1
for i in range(M):
    a,b = map(int,input().split())
    if ls[a-1] == 0 and ls[b-1]==0:
        ls[a-1]=flg
        ls[b-1]=flg
        flg+=1
    elif ls[a-1] == 0:
        ls[a-1] = ls[b-1]
    elif ls[b-1] == 0:
        ls[b-1] = ls[a-1]
    else:
        check = min(ls[a-1],ls[b-1])
        ls[a-1] = check
        ls[b-1] = check
import collections
c = collections.Counter(ls)
plan = c.most_common()
ans = 0
if plan[0][0] == 0:
    ans = plan[1][1]
else:
    ans = plan[0][1]
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = map(int,input().split())
uf = UnionFind(n)
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)
ans = 0
for j in range(n):
    check = uf.size(j)
    if ans < check:
        ans = check
print(ans)
l = int(raw_input())
print (len(set(map(int, raw_input().split())))//2)*2

### FIXED CODE ###

r = int(raw_input())
print ("ABC" if r<1200 else "ARC")
t = int(input())

for i in range(t):
    n, k, d = map(int, input().split())
    n = abs(n)
    ok = n // d
    left = k - (ok)
    if left % 2:
        print(d - (n%d))
    else:
        print(n%d)

### FIXED CODE ###

n, k, d = map(int, input().split())
n = abs(n)
ok = n // d
if k < ok:
  print(n - (k*d))
else:
  left = k - (ok)
  if left % 2:
  	print(d - (n%d))
  else:
    print(n%d)
N = int(input())
if N == 1
  print("Hello World")
  exit()
else:
  A = int(input())
  B = int(input())
  print(A+B)

### FIXED CODE ###

N = int(input())
if N == 1:
  print("Hello World")
  exit()
else:
  A = int(input())
  B = int(input())
  print(A+B)
def 解()
    iN = int(input())
    aA = [int(_) for _ in input().split()]
    iL = len(aA)


    iStart = 0
    if sum(aA[0::2]) < sum(aA[2::2]):
        iStart = 1


    iC = 0
    aD = [0]*iL
    if 0 % 2 == iStart :
        if aA[0] < 0:
            aA[0] = 1
            iC += -1 * aA[0] + 1
    else:
        if 0 < aA[0] :
            aA[0] = -1
            iC += aA[0] + 1

    aD[0] = aA[0]
    for i in range(1,iL):
        aD[i] = aD[i-1]+aA[i]
        if i % 2 == iStart:
            if aD[i] <= 0:
                iC += -1*aD[i] +1
                aD[i] = 1
        else:
            if aD[i] >= 0:
                iC += aD[i] +1
                aD[i] = -1
    print(iC)
解()


### FIXED CODE ###

#結局これもパターン全列挙(2パターン)か。
#判別しようと無駄な努力をしてしまった。
def 解():
    iN = int(input())
    aA = [int(_) for _ in input().split()]
    def buildDiff(bF):
        iC = 0
        iS = 0
        for a in aA:
            iS += a
            if bF:
                if iS >= 0:
                    iC += iS + 1
                    iS = -1
                bF = 0
            else:
                if iS <= 0:
                    iC += -1 * iS + 1
                    iS = 1
                bF = 1
        return iC
    print(min(buildDiff(1),buildDiff(0)))
解()
a,b=map(int,input(),split())
print(a+b//2)

### FIXED CODE ###

a,b=map(int,input().split())
print(a+b//2)
import collections

N=list(map(int,input().split(" ")))
list_odd=N[::2]
list_even=N[1::2]
c_odd = collections.Counter(list_odd)
c_even = collections.Counter(list_even)
most_odd=c_odd.most_common()[0][1]
most_even=c_even.most_common()[0][1]
print(len(list_even)+len(list_odd)-most_even-most_odd)


### FIXED CODE ###

import collections
n=int(input())
N=list(map(int,input().split(" ")))
list_odd=N[::2]
list_even=N[1::2]
c_odd = collections.Counter(list_odd)
c_even = collections.Counter(list_even)
most_odd=c_odd.most_common()[0][1]
most_even=c_even.most_common()[0][1]
if (n<=2):
    print("0")
elif (len(list_even)==most_even and len(list_odd)==most_odd and c_odd.most_common()[0][0]==c_even.most_common()[0][0]):
    print(most_odd)
else:
    if(c_odd.most_common()[0][0]==c_even.most_common()[0][0]):
        M=max(c_odd.most_common()[1][1],c_even.most_common()[1][1])
        print(min((len(list_even)+len(list_odd)-M-most_odd),(len(list_even)+len(list_odd)-M-most_even)))
    else:
        print(len(list_even)+len(list_odd)-most_even-most_odd)
#c_odd.most_common()[0][0]==c_even.most_common()[0][0]
A,B,C,D = map(int,input().split())

Takahashi = A
Aoki = B

while Takahashi <= 0 or Aoki <=0:
  Aoki -= B
  if Aoki <= 0:
    print('Yes')
    break
  Takahashi -= D
  if Takahashi <= 0:
    print('No')
    break

### FIXED CODE ###

S,W = map(int,input().split())
 
if S <= W:
  print('unsafe')
else:
  print('safe')
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

dp = [[float("inf")] * (W+1) for _ in range(H+1)]
dp[0][1] = 0
dp[1][0] = 0

for y in range(W):
    for x in range(H):
        dp[y+1][x+1] = min(
            dp[y][x+1] + (s[y][x] == '#' and (y == 0 or s[y-1][x] == '.')),
            dp[y+1][x] + (s[y][x] == '#' and (x == 0 or s[y][x-1] == '.'))
        )

print(dp[-1][-1])


### FIXED CODE ###

H, W = map(int,input().split())
board = []
for h in range(H):
    board.append(input())

dp=[[1000 for i in range(W+1)] for j in range(H+1)]
dp[0][1] = 0
dp[1][0] = 0

for h in range(H):
    for w in range(W):
        dp[h+1][w+1] = min(
            dp[h][w+1] + (board[h][w]=='#' and (h==0 or board[h-1][w]=='.')),
            dp[h+1][w] + (board[h][w]=='#' and (w==0 or board[h][w-1]=='.'))
        )

print (dp[-1][-1])
n,m,p = map(int,input().split())
E1 = [[] for i in range(n)]
E2 = [[] for i in range(n)]
edge = []
for i in range(m):
    a,b,c = map(int,input().split())
    c = p-c
    a -= 1
    b -= 1
    E1[a].append(b)
    E2[b].append(a)
    edge.append((a,b,c))

dis1 = [False]*n
def dfs1(x):
    if dis1[x] == True:
        return
    dis1[x] = True
    for nex in E1[x]:
        dfs1(nex)

dis2 = [False]*n
def dfs2(x):
    if dis2[x] == True:
        return
    dis2[x] = True
    for nex in E2[x]:
        dfs2(nex)

dfs1(0)
dfs2(n-1)

ok = []
for i,j in zip(dis1,dis2):
    if i == True and j == True:
        ok.append(True)
    else:
        ok.append(False)
nedge = []
for a,b,c in edge:
    if ok[a] and ok[b]:
        nedge.append((a,b,c))

edge = nedge
def belw():
    dis = [float("INF")]*n
    dis[0] = 0
    count = 0
    check = True

    while check:
        check = False
        for a,b,c in edge:
            
            if dis[a] != float("INF") and dis[b] > dis[a]+c:
                check = True
                dis[b] = dis[a]+c
        count += 1

        if count > n+1 and check:
            return float("INF")
    
    return -dis[-1]

ans = belw()
if ans == float("INF"):
    print(-1)
else:
    print(max(ans,0))











### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m,p = map(int,input().split())
E1 = [[] for i in range(n)]
E2 = [[] for i in range(n)]
edge = []
for i in range(m):
    a,b,c = map(int,input().split())
    c = p-c
    a -= 1
    b -= 1
    E1[a].append(b)
    E2[b].append(a)
    edge.append((a,b,c))

dis1 = [False]*n
def dfs1(x):
    if dis1[x] == False:
        dis1[x] = True
        for nex in E1[x]:
            dfs1(nex)

dis2 = [False]*n
def dfs2(x):
    if dis2[x] == False:
        dis2[x] = True
        for nex in E2[x]:
            dfs2(nex)

dfs1(0)
dfs2(n-1)

ok = []
for i in  range(n):
    if dis1[i] and dis2[i]:
        ok.append(True)
    else:
        ok.append(False)
nedge = []
for a,b,c in edge:
    if ok[a] and ok[b]:
        nedge.append((a,b,c))

def belw():
    dis = [float("INF")]*n
    dis[0] = 0
    count = 0
    check = True

    while check:
        check = False
        for a,b,c in nedge:
            
            if dis[a] != float("INF") and dis[b] > dis[a]+c:
                check = True
                dis[b] = dis[a]+c
        count += 1

        if count > n+1 and check:
            return float("INF")
    
    return -dis[-1]

ans = belw()
if ans == float("INF"):
    print(-1)
else:
    print(max(ans,0))