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

count = 0

def marge(A,left,mid,right):
    global count
    n1 = mid -left
    n2 = right -mid
    L = []
    R = []
    for i in range(left,n1+left):
        L.append(A[i])
    for i in range(mid,n2+mid):
        R.append(A[i])

    L.append(float("inf"))
    R.append(float("inf"))

    r_id,l_id = 0,0
    for k in range(left,right):
        count += 1
        if(L[l_id] <= R[r_id]):
            A[k] = L[l_id]
            l_id += 1
        else:
            A[k] = R[r_id]
            r_id += 1

def margeSort(A,left,right):
    if left+1 < right:
        mid = int((left+right)/2)
        margeSort(A,left,mid)
        margeSort(A,mid,right)
        marge(A,left,mid,right)


n = int(input())
s = input()
A = []
A = list(map(int,s.split()))

margeSort(A,0,n)

A_str = map(str,A)
print(" ".join(list(A_str)))
print(count)

### FIXED CODE ###

count = 0

def marge(A,left,mid,right):
    global count
    n1 = mid -left
    n2 = right -mid
    L = []
    R = []
    for i in range(left,n1+left):
        L.append(A[i])
    for i in range(mid,n2+mid):
        R.append(A[i])

    L.append(float("inf"))
    R.append(float("inf"))

    r_id,l_id = 0,0
    for k in range(left,right):
        count += 1
        if(L[l_id] <= R[r_id]):
            A[k] = L[l_id]
            l_id += 1
        else:
            A[k] = R[r_id]
            r_id += 1

def margeSort(A,left,right):
    if left+1 < right:
        mid = int((left+right)/2)
        margeSort(A,left,mid)
        margeSort(A,mid,right)
        marge(A,left,mid,right)


n = int(raw_input())
s = raw_input()
A = []
A = map(int,s.split())

margeSort(A,0,n)

A_str = map(str,A)
print(" ".join(list(A_str)))
print count
### BUGGY CODE ###

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
w=[items[i][0] for i in range(n)]
v=[items[i][1] for i in range(n)]

memo=[[-1]*(W+1) for i in range(n+1)]
def dfs(i,j):
  global memo
  if memo[i][j]>=0:
    return memo[i][j]
  else :
    if i==n:
      memo[i][j]=0
    elif j<w[i]:
      memo[i][j]=dfs(i+1,j)
    else:
      memo[i][j]=max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])
  return memo[i][j]

print(dfs(0,W))

### FIXED CODE ###

import sys
input=sys.stdin.readline

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
import numpy as np

dp=np.zeros([n+1,W+1],dtype=np.int64)
for i in range(n):
  w=items[i][0]
  v=items[i][1]
  dp[i+1][:w]=dp[i][:w]
  dp[i+1][w:]=np.maximum(dp[i][w:],dp[i][:-w]+v)
print(dp[-1][-1])
### BUGGY CODE ###

x,y,z,k = input().strip().split(' ')
x,y,z,k = [int(x), int(y),int(z),int(k)]
aList = list(map(int, input().strip().split(' ')))
bList = list(map(int, input().strip().split(' ')))
cList = list(map(int, input().strip().split(' ')))
ansList = []
for i in range(len(aList)):
        for j in range(len(bList)):
                for n in range(len(cList)):
                        y = aList[i] + bList[j] + cList[n]
                        ansList.append(y)
ansList.sort(reverse = True)

for i in range(k):
        print(ansList[i])


### FIXED CODE ###

x,y,z,k = input().strip().split(' ')
x,y,z,k = [int(x), int(y),int(z),int(k)]
aList = list(map(int, input().strip().split(' ')))
bList = list(map(int, input().strip().split(' ')))
cList = list(map(int, input().strip().split(' ')))
ansList = []
# aList.sort(reverse = True)
# bList.sort(reverse = True)
# cList.sort(reverse = True)

abList = []
for i in range(len(aList)):
        for j in range(len(bList)):
                abList.append(aList[i] + bList[j])
abList.sort(reverse = True)
abcList = []
for s in range(min(len(abList),k)):
        for t in range(len(cList)):
                abcList.append(abList[s] + cList[t])
abcList.sort(reverse = True)
for a in range(min(len(abcList),k)):
        print(abcList[a])
### BUGGY CODE ###

import numpy as np
import math
import collections
import bisect
#import sympy


def divisor(n):
    i = 1
    lower_divisors, upper_divisors = [], []
    while(i * i <= n):
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


N = int(input())

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

A.sort()

ans = 0
ans = N
Set = set()
for i in range(N):
    divs = divisor(A[i])
    # print(divs)
    if i != 0:
        Set.add(A[i - 1])
    if i < N - 1:
        if A[i] == A[i + 1]:
            ans -= 1
            continue

    for d in divs:
        if i != 0:
            if d in Set:
                ans -= 1
                break
print(ans)


### FIXED CODE ###

import numpy as np
import math
import collections
import bisect
from collections import Counter


N = int(input())

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

A.sort()
Set = set()

Amax = A[len(A) - 1]

counter = Counter(A)
ans = 0
for a in A:
    if a in Set:
        continue
    x = a
    while(x <= Amax):
        Set.add(x)
        x += a

    if counter[a] == 1:
        ans += 1

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

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

ans=9999999999

n1=min(min(A),max(A)-N)
n2=max(A)

for b in range(n1,n2):
    num=0
    for i,a in enumerate(A):
        num += abs(a-(b+i+1))
    if num<ans: 
        ans=num
print(ans)

### FIXED CODE ###

import numpy as np

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

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

b=np.median(AA)
ans=0

for a in AA:
    ans+=abs(a-b)
print(int(ans))
### BUGGY CODE ###

n,k,q = map(int,input().split())
a = [0] * q
for i in range(q):
  a[i] = int(input())
for i in range(1,n +1):
  c = q - a.count(i)
  if k - c > 0 :
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n,k,q = map(int,input().split())
a = [0] * q
b = [0] * (n + 1)
for i in range(q):
  a = int(input())
  b[a] += 1

m = q - k + 1
for i in range(1,n +1):
  if b[i] >= m:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

N = int(input())

itemCount = 0
itemList = []

for i in range(N):
  item = input()
  if item not in itemList:
    itemCount += 1
    itemList.append(item)

print(itemCount)

### FIXED CODE ###

N = int(input())

itemCount = 0
itemList = {}

for i in range(N):
  item = input()
  if item in itemList:
    continue
  else:
    itemCount += 1
    itemList[item] = item

print(itemCount)
### BUGGY CODE ###

#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

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

A = []
B = []

for _ in range(M):
    a,b = map(int, input().split())
    if a == 1: A.append(b)
    elif b == N: B.append(a)

for a in A:
    if a in B:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

### FIXED CODE ###

#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

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

A = []
B = []

for _ in range(M):
    a,b = map(int, input().split())
    if a == 1: A.append(b)
    elif b == N: B.append(a)

B.sort()
for a in A:
    if bisect.bisect_left(B, a) < len(B) and B[bisect.bisect_left(B, a)]==a:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

from collections import defaultdict
s = input()
n = len(s)
target = 2019
res = 0
dic = defaultdict(int)
for i in range(n):
    dic[int(s[i:]) % target] += 1
for i in range(2018):
    res += dic[i] * (dic[i] -1) //2
res += dic[0]
print(res)

### FIXED CODE ###

from collections import defaultdict
s = input()
n = len(s)
target = 2019
res = 0
dic = defaultdict(int)
dic[0] = 1
s = s[::-1]
num, d = 0, 1
for char in s:
    num += int(char) * d
    num %= target
    d *= 10
    d %= target
    dic[num] += 1
for i in dic.values():
    res += i * (i -1) //2
print(res)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  x=a.index(i+1)
  b.append(str(x+1))
print(" ".join(b))

  

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
  b[a[i]-1]=str(i+1)
print(" ".join(b))
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
suji = []
for i in range(b):
    if a+i<=b:
        suji.append(a+i)
    else:
        pass
count=0
for j in range(len(suji)):
    if suji[j]%c==0 or suji[j]%d==0:
        count+=0
    else:
        count+=1
print(count)

### FIXED CODE ###

a,b,c,d = map(int,input().split())
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)

A = (a-1)//c + (a-1)//d - (a-1)//lcm(c,d)
B = b//c + b//d -b//lcm(c,d)

print((b-B)-((a-1)-A))
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
    
h, w = MAP()
s = [STR() for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
arr[0][0] = 0
que = deque([[0, 0]])
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while que:
    y, x = map(int, que.popleft())
    if s[y][x] == '.':
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                tmp = arr[y][x]
                arr[y][x] = min(arr[y][x], arr[ny][nx] + 1)
                if arr[ny][nx] >= inf:
                    que.append([ny, nx])
if arr[h - 1][w - 1] >= inf:
    print(-1)
    exit()
ss = 0
for i in range(h):
    ss += s[i].count('.')
print(ss - arr[h - 1][w - 1] - 1)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
s = [STR() for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
arr[0][0] = 0
que = deque([[0, 0]])
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while len(que):
    y, x = map(int, que.popleft())
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < h and 0 <= nx < w:
            tmp = arr[y][x]
            arr[y][x] = min(arr[y][x], arr[ny][nx] + 1)
            if arr[ny][nx] >= inf and s[ny][nx] == '.' and not [ny, nx] in que:
                que.append([ny, nx])
    if y == h - 1 and x == w - 1:
        break
if arr[h - 1][w - 1] >= inf:
    print(-1)
    exit()
ss = 0
for i in range(h):
    ss += s[i].count('.')
print(ss - arr[h - 1][w - 1] - 1)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
x = 1
for i in range(N):
    x *= A[i]
if x > 10**18:
    x = -1
print(x)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
x = 1
if 0 in A:
    x = 0
else:
    for i in range(N):
        x *= A[i]
        if x > 10**18:
            x = -1
            break
print(x)
### BUGGY CODE ###

p=0
N,K=map(int,input().split())
a,b,c=map(int,input().split())
s=input()
L=list()
for i in range(N):
  if i<K:
    if s[i]=="r":
      p+=c
      L.append(i)
    elif s[i]=="s":
      p+=a
      L.append(i)
    else:
      p+=b
      L.append(i)
  else:
    if s[i]=="r" and s[i-K]!="r":
      p+=c
      L.append(i)
    elif s[i]=="s" and s[i-K]!="s":
      p+=a
      L.append(i)
    elif s[i]=="p" and s[i-K]!="p":
      p+=b
      L.append(i)
    if s[i]=="r" and s[i-K]=="r" and i-K not in L:
      p+=c
      L.append(i)
    if s[i]=="s" and s[i-K]=="s" and i-K not in L:
      p+=a
      L.append(i)
    if s[i]=="p" and s[i-K]=="p" and i-K not in L:
      p+=b
      L.append(i)
print(p)

### FIXED CODE ###

p=0
N,K=map(int,input().split())
a,b,c=map(int,input().split())
s=input()
L=list()
L_append = L.append
for i in range(N):
  if i<K:
    if s[i]=="r":
      p+=c
      L_append(i)
    elif s[i]=="s":
      p+=a
      L_append(i)
    else:
      p+=b
      L_append(i)
  else:
    if s[i]=="r" and s[i-K]!="r":
      p+=c
      L_append(i)
    elif s[i]=="s" and s[i-K]!="s":
      p+=a
      L_append(i)
    elif s[i]=="p" and s[i-K]!="p":
      p+=b
      L_append(i)
    if s[i]=="r" and s[i-K]=="r" and i-K not in L:
      p+=c
      L_append(i)
    elif s[i]=="s" and s[i-K]=="s" and i-K not in L:
      p+=a
      L_append(i)
    elif s[i]=="p" and s[i-K]=="p" and i-K not in L:
      p+=b
      L_append(i)
print(p)
### BUGGY CODE ###

h, n = (int(x) for x in input().split())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
dp = [float('inf')] * (h)
for a, b in ab:
    for i in range(h):
        if i < a:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i - a] + b)
print(dp[h - 1])

### FIXED CODE ###

h, n = (int(x) for x in input().split())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
max_a = max(a for a, _ in ab)
dp = [0] * (h + max_a)
for i in range(1, h + 1):
    dp[i] = min(dp[i - a] + b for a, b in ab)
print(dp[h])
### BUGGY CODE ###

import numpy as np
_NM = input().split()

N = int(_NM[0])
M = int(_NM[1])

a = []
b = []

for _ in range(N):
  _ab = input().split()
  a.append(int(_ab[0]))
  b.append(int(_ab[1]))
  
#a = np.array(a)
#b = np.array(b)

_c = zip(a,b)
_c = sorted(_c, key=lambda x:(x[0],-x[1]))
a,b = zip(*_c)
a,b = np.array(list(a)), np.array(list(b))
#print(a,b)
ret = 0
for d in range(M+1):
  # dより小さいaを指定し，該当するようなbを抽出
  inds = np.where(a<=d)[0]
  if len(inds)<=0:
    continue
  b_extracted = b[inds]
  
  b_max = max(b_extracted)
  ret += b_max
  inds_max = np.where(b==b_max)[0] # <= npwhereの返す配列がおかしい．．．ので[0]が必要
  #print(inds_max[0],b_max)
  #print('before a and b:',a,b,)
  a = np.delete(a,inds_max[0])
  b = np.delete(b,inds_max[0])
  #print('after a and b:',a,b,)
print(ret)

### FIXED CODE ###

import numpy as np
import heapq
N,M = map(int,input().split())
jobs = [[] for _ in range(10 ** 5 + 1)]

for _ in range(N):
  a,b = map(int,input().split())
  jobs[a].append(b)
ans = 0
heap = []
for d in range(M+1):
  if jobs[d]: #空でないなら
    for _b in jobs[d]:
      heapq.heappush(heap,-_b) #heappopは最小値を返すので-をつけておく
  if heap: #空でないなら
    ans += -heapq.heappop(heap) #最小値を返してpop
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
k = m
while True:
    if m % k == 0 and m // k >= n:
        print(k)
        break
    k -= 1

### FIXED CODE ###

n,m = map(int,input().split())
divisors = []
for i in range(1,int(m**0.5)+1):
    if m % i == 0:
        divisors.append(i)
        divisors.append(m//i)
divisors.sort()
k = 0
for i in range(len(divisors)):
    if divisors[i] > m/n:
        k = i - 1
        break
    if i == len(divisors) - 1:
        k = len(divisors) - 1
print(divisors[k])
### BUGGY CODE ###

from math import gcd

k = int(input())

sum = 0
i, j = 0, 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            i = gcd(gcd(a, b), c)
            sum += i

print(sum)

### FIXED CODE ###

from math import gcd

k = int(input())

sum = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            sum += gcd(gcd(a, b), c)

print(sum)
### BUGGY CODE ###

from collections import deque
N,M,K = map(int,input().split())
F = {i:set() for i in range(1,N+1)}
B = {i:set() for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    F[a].add(b)
    F[b].add(a)
for _ in range(K):
    c,d = map(int,input().split())
    B[c].add(d)
    B[d].add(c)
A = []
hist = [-1 for _ in range(N+1)]
cnt = -1
for i in range(1,N+1):
    if hist[i]<0:
        cnt += 1
        A1 = set()
        que = deque([i])
        hist[i] = cnt
        A1.add(i)
        while que:
            x = que.popleft()
            for y in F[x]:
                if hist[y]<0:
                    A1.add(y)
                    que.append(y)
                    hist[y]=cnt
        A.append(A1)
C = []
for i in range(1,N+1):
    cnt = hist[i]
    C.append(len(A[cnt]-F[i]-B[i])-1)
print(*C)   

### FIXED CODE ###

def rt(x):
    while x!=T[x][0]:
        x = T[x][0]
    return x
N,M,K = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
D = {i:[] for i in range(1,N+1)}
for _ in range(K):
    c,d = map(int,input().split())
    D[c].append(d)
    D[d].append(c)
T = {i:[i,0] for i in range(1,N+1)}
for a in G:
    for b in G[a]:
        r1 = rt(a)
        r2 = rt(b)
        if r1!=r2:
            if T[r1][1]>=T[r2][1]:
                T[r2][0] = r1
                if T[r1][1]==T[r2][1]:
                    T[r1][1] += 1
            else:
                T[r1][0] = r2
C = {}
for i in range(1,N+1):
    rt1 = rt(i)
    if rt1 not in C:
        C[rt1] = 0
    C[rt1] += 1
B = [0 for _ in range(N+1)]
for i in range(1,N+1):
    rt1 = rt(i)
    numc = C[rt1]
    numd = len(G[i])
    B[i] = numc-1-numd
    for j in D[i]:
        if rt(j)==rt1:
            B[i] -= 1
print(*B[1:])
### BUGGY CODE ###

from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

s = input()[::-1]
rem = [[0 for i in range(13)] for _ in range(len(s)+1)]
rem[0][0] = 1
for i, st in enumerate(s):
    if st == '?':
        for j in range(10):
            next = j * 10 ** i
            for k in range(13):
                rem[i+1][(k+next)%13] += rem[i][k]
    else:
        next = int(st) * 10**i
        for j in range(13):
            rem[i+1][(j+next)%13] = rem[i][j]
    for _ in range(13):
        rem[i+1][_] %= mod
print(rem[len(s)][5]%mod)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = sys.stdin.readline()
n = len(s)-1
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1#桁
    m = pow(10,c,13)
    if s[i] == '?':
        for k in range(10):
            l = (m*k) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        k = int(s[i])
        l = (m*k) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]
    # print(now)
print(now[5])
### BUGGY CODE ###

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

max = []
for i in range(N-K+1):
    #print(i)
    target = P[i:i+K]
    #print(target)
    if sum(max) < sum(target):
        max = target

#print(max)
ans = []
for i in max:
    ans.append((i*(1+i)/2)/i)

print(sum(ans))


### FIXED CODE ###

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

''' 累積和 '''
cumulative_sum = [P[0]]
for i in range(len(P)-1):
    cumulative_sum.append(cumulative_sum[i] + P[i+1])

#入力
#print(P)
#累積和
#print(cumulative_sum)

#numpy 累積和（高速）
#import numpy
#res = numpy.cumsum(P)
#print(res)

''' 最大値探索 O(N-K) '''
#初期値
max = cumulative_sum[K-1]
max_index = 0
for i in range(N-K):
    now = cumulative_sum[K+i] - cumulative_sum[i]
    if max < now:
        max = now
        index = i
#print(max)
#print(max_index)


ans = (max + K)/2
print(ans)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
x_sorted = sorted(x)

cs = x_sorted[n // 2 - 1]
cb = x_sorted[n // 2]

for i, v in enumerate(x):
    if x_sorted.index(v) < n // 2:
        print(cb)
    else:
        print(cs)


### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
x_sorted = sorted(x)

cs = x_sorted[n // 2 - 1]
cb = x_sorted[n // 2]

for i, v in enumerate(x):
    if v <= cs:
        print(cb)
    else:
        print(cs)
### BUGGY CODE ###

S=input()
MOD=10**9+7
dp=[0]*13
dp[0]=1
for i in range(len(S)):
    new_dp=[0]*13
    s=S[-1-i]
    if s=="?":
        for j in range(10):
            for k in range(13):
                new_dp[(k+j*10**i)%13]+=dp[k]
    else:
        for k in range(13):
            new_dp[(k+int(s)*10**i)%13]+=dp[k]
    for l in range(13):
        new_dp[l]%=MOD
    dp=new_dp
print(dp[5])

### FIXED CODE ###

S=input()
MOD=10**9+7
dp=[0]*13
dp[0]=1
r=1
for i in range(len(S)):
    new_dp=[0]*13
    s=S[-1-i]
    if s=="?":
        for j in range(10):
            rem=(j*r)%13
            for k in range(13):
                new_dp[(k+rem)%13]+=dp[k]
    else:
        rem=(int(s)*r)%13
        for k in range(13):
            new_dp[(k+rem)%13]+=dp[k]
    for l in range(13):
        new_dp[l]%=MOD
    dp=new_dp
    r=(r*10)%13
print(dp[5])
### BUGGY CODE ###

import sys
def main():
    N, M, P = map(int, input().split())
    Edge = []
    for i in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        a, b = a - 1, b - 1
        c = -(c - P)
        Edge.append([a, b, c])

    # ベルマンフォード
    dist = [float('inf')] * N
    dist[0] = 0

    for i in range(2 * N):
        for fr, to, cost in Edge:
            if (dist[fr] != float('inf')) and (dist[to] > dist[fr] + cost):
                dist[to] = dist[fr] + cost
                if (i >= N) & (to == N - 1):
                    print(-1)
                    exit()

    print(max(0, -dist[N - 1]) if -dist[N - 1] != float('inf') else 0)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
N, M, P = map(int, input().split())
Edge = []
G = [[] for i in range(N)]
G_rev = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    a, b = a - 1, b - 1
    c = -(c - P)
    Edge.append([a, b, c])
    G[a].append(b)
    G_rev[b].append(a)


# 0とNの両方から辿れない頂点を削除
def dfs(g, stack):
    can_reach = set()
    while stack:
        n = stack.pop()
        can_reach.add(n)
        for to in g[n]:
            if to in can_reach:
                continue
            stack.append(to)
    return can_reach


can_reach_from_0 = dfs(G, [0])
can_reach_from_N = dfs(G_rev, [N - 1])

can_reach_from_0_and_N = can_reach_from_0 & can_reach_from_N
EdgeShifted = []
for a, b, c in Edge:
    if (a in can_reach_from_0_and_N) and (b in can_reach_from_0_and_N):
        EdgeShifted.append([a, b, c])


# ベルマンフォード
dist = [float('inf')] * N
dist[0] = 0

for n in range(len(can_reach_from_0_and_N)):
    for fr, to, cost in EdgeShifted:
        if dist[to] > dist[fr] + cost:
            dist[to] = dist[fr] + cost
            # 負閉路検出
            if n == len(can_reach_from_0_and_N) - 1:
                print(-1)
                exit()

print(max(0, -dist[N - 1]))