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

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    L,A,B,M=map(int,input().split())
    S=lambda i:A+B*i
    sec=[]
    
    def nibutan(ok,ng,k):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid,k):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid,k):
        return len(str(S(mid)))<k
    
    left=L-1
    for k in range(19,0,-1):
        if len(str(S(left)))==k:
            right=nibutan(-1,left,k)
            sec.append((k,left,right))
            left=right
    
    def modinv(a, mod=M):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    
    ans=0
    c=0
    for k,left,right in sec:
        C=pow(10,k)
        n=left-right
        ans+=(S(left)*(pow(C,n)-1)-B*((n-1)*pow(C,n)-(pow(C,n)-1)//(C-1)+1))//(C-1)*pow(10,c)
        ans%=M
        c+=n*k
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
import numpy as np
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    L,A,B,M=map(int,input().split())
    S=lambda i:A+B*i
    sec=[]
    
    def nibutan(ok,ng,k):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid,k):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid,k):
        return len(str(S(mid)))<k
    
    left=L-1
    for k in range(19,0,-1):
        if len(str(S(left)))==k:
            right=nibutan(-1,left,k)
            sec.append((k,left,right))
            left=right
    
    X=np.array([0,A%M,1],dtype=np.int64)
    for k,left,right in sec[::-1]:
        n=left-right
        doubling=[np.array([[pow(10,k,M),0,0],[1,1,0],[0,B%M,1]],dtype=np.int64)]
        for i in range((10**18).bit_length()):
            doubling.append(np.dot(doubling[i],doubling[i])%M)
        n=left-right
        for i in range(len(doubling)):
            if n&1:
                X=np.dot(X,doubling[i])%M
            n>>=1
            if n==0:
                break
    print(X[0])

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

l,r = map(int,input().split())
s = 2019
for k in range(l,r):
    i = k
    for l in range(i+1,r+1):
        j = l
        if s > i*j%2019:
            s = i*j%2019
print(s)

### FIXED CODE ###

l,r = map(int,input().split())
r=min(r,l+2019)
s = 2019
for k in range(l,r):
    i = k
    for l in range(i+1,r+1):
        j = l
        mo = (i*j)%2019
        if s > mo:
            s = mo
print(s)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
def last_k(a, i):
    p = 1
    for j in range(k):
        p=p*a[i-j]
    return p
for i in range(n-k):
    if last_k(a, i+k-1) < last_k(a, i+k):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

for i in range(n-k):
    if a[i+k] > a[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from functools import reduce
from fractions import gcd
from collections import Counter


def least_common_multiple(iter):
    '''
    最小公倍数を返す
    '''
    lcm = lambda x, y: x*y//gcd(x, y)
    return reduce(lcm, iter)


N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
l = least_common_multiple(list(c.keys()))
ans = 0
MOD = 10**9+7
for k, v in c.items():
    ans = (ans + (l // k * v) % MOD) % MOD
print(ans)


### FIXED CODE ###

from fractions import gcd


N = int(input())
A = list(map(int, input().split()))
lcm = lambda x, y: x*y//gcd(x, y)
l = 1
for a in A:
    l = lcm(l, a)
ans = 0
MOD = 10**9+7
for a in A:
    ans += l // a
print(ans % MOD)
### BUGGY CODE ###

n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

dp = [[0]*(w+10) for i in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j-wv[i][0] >= 0:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j-wv[i][0]]+wv[i][1])
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])

print(max(dp[-1]))


### FIXED CODE ###

n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

dp = [[0]*(w+10) for i in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j-wv[i][0] >= 0:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j-wv[i][0]]+wv[i][1])
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])

print(max(dp[-1]))
### BUGGY CODE ###

# 2019-11-18 17:34:23(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n, m, *a = [int(x) for x in sys.stdin.read().split()]

    for _ in range(m):
        a.sort()
        a[-1] //= 2
    
    print(sum(a))
        


if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-18 17:34:23(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    a = [-int(x) for x in sys.stdin.readline().split()]

    heapq.heapify(a)
    for _ in range(m):
        highest = - heapq.heappop(a)
        heapq.heappush(a, -(highest // 2))
    
    print(-sum(a))
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    k = kwargs["k"]
    res = 0
    p = 7
    rs = 0

    while True:
        res += 1
        r = p % k
        rs += r
        if rs % k == 0:
            break
        if r == 0:
            res = -1
            break
        p = r * 10


    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["k"] = [int(i) for i in cin][0]

    cout = main(kwargs)
    print(cout)

### FIXED CODE ###

import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    k = kwargs["k"]
    res = 0
    p = 7
    rs = 0

    while True:
        res += 1
        r = p % k
        rs += r
        if rs % k == 0:
            break
        if r == 0 or res > 1000000:
            res = -1
            break
        p = r * 10


    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["k"] = [int(i) for i in cin][0]

    cout = main(kwargs)
    print(cout)
### BUGGY CODE ###

import math
import sys

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:


        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result





arr_data = getinputdata()

#maxvalue
k = int(arr_data[0][0])

#sumvalue
s = int(arr_data[0][1])


#print(k,s)

cnt=0

for x in range(0,k+1):
    
    for y in range(0,k+1):
    
        for z in range(0,k+1):
        
            if s<x or s<y or s<z:
                
                break
            
            if x+y+z==s:
                
                cnt+=1
                
print(cnt)
                

### FIXED CODE ###

def getinputdata():

    array_result = []
    
    data = input()
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result

arr_data = getinputdata()

#maxvalue
k = int(arr_data[0][0])

#sumvalue
s = int(arr_data[0][1])

cnt = 0

for x in range(0, k + 1):
    
    for y in range(0, k + 1):
        
        z = s-x-y
        
        if z >= 0 and z <= k:
            
            cnt += 1
            
print(cnt)
### BUGGY CODE ###

S=input()


S=[s for s in S]

count=0
i=0
while(i<len(S)-1):
#	print(i,S)
	if(int(S[i])+int(S[i+1])==1):
		count+=2
		if(i<=len(S)-3):
			S=S[:i]+S[i+2:]
		elif(i==len(S)-2):
			break
				
		if(i>0):
			i-=1
	else:
		i+=1

print(count)

### FIXED CODE ###

S=input();print(min(S.count("1"),S.count("0"))*2)
### BUGGY CODE ###

from operator import itemgetter

n, a, b = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(itemgetter(0), sorted(enumerate(ppp, start=1), key=itemgetter(1))))
INF = 10 ** 15

dp = {0: 0}
for i in qqq:
    ndp = {}
    tmp_min_cost = INF
    stay_min_cost = INF
    for j, cost in sorted(dp.items()):
        if j <= i:
            if j < i:
                stay_min_cost = min(stay_min_cost, cost)
            cost += b
            if tmp_min_cost > cost:
                ndp[j] = tmp_min_cost = cost
        else:
            cost += a
            if tmp_min_cost > cost:
                ndp[j] = tmp_min_cost = cost
    if stay_min_cost < INF:
        ndp[i] = min(ndp[i], stay_min_cost) if i in ndp else stay_min_cost
    dp = ndp

print(min(dp.values()))


### FIXED CODE ###

from bisect import bisect
from operator import itemgetter

n, a, b = map(int, input().split())
ppp = map(int, input().split())
qqq = [i for i, p in sorted(enumerate(ppp, start=1), key=itemgetter(1))]
INF = 10 ** 15

dp = [(0, 0)]
for i in qqq:
    ndp = []
    s = bisect(dp, (i,))
    tmp_min = INF
    for j, cost in dp[:s]:
        cost += b
        ndp.append((j, cost))
        tmp_min = cost
    stay_cost = dp[s - 1][1]
    if tmp_min > stay_cost:
        ndp.append((i, stay_cost))
        tmp_min = stay_cost
    for j, cost in dp[s:]:
        cost += a
        if tmp_min > cost:
            ndp.append((j, cost))
            tmp_min = cost
    dp = ndp

print(dp[-1][1])
### BUGGY CODE ###

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

for i in range(1,N+1) :
    print(A.count(i))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B={}
for i in range(1,N+1):
    B[i]=0

for j in A:
    B[j]+=1

for l in B.values():
    print(l)
### BUGGY CODE ###

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

l=[]
for i in range(n):
  a,b=map(int, input().split())
  l.append([a]*b)
ll=[]
for i in l:
  for j in i:  
    ll.append(j)
 
ll=sorted(ll)
print(ll[k-1])


### FIXED CODE ###

n,k=map(int,input().split())
li = [list(map(int, input().split())) for i in range(n)]
li.sort()
c=0
for i in range(n):
  c+=li[i][1]
  if c>=k:
    print(li[i][0])
    
    break
### BUGGY CODE ###

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

INFTY = 1000000001
cnt = [0]

def merge(left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [0 for _ in range(n1+1)]
    R = [0 for _ in range(n2+1)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = INFTY
    R[n2] = INFTY
    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(left, right):
    if left+1 < right:
        mid = int((left+right) / 2)
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)

merge_sort(0, N)
print(" ".join(map(str, A)))


### FIXED CODE ###

def counting_sort(MAX):
    C = [0 for _ in range(MAX+1)]

    for i in range(N):
        C[A[i]] += 1

    for i in range(1, MAX+1):
        C[i] = C[i] + C[i-1]

    for i in range(N-1, -1, -1):
        C[A[i]] -= 1
        B[C[A[i]]] = A[i]

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

MAX = 10001

B = [0 for _ in range(N)]
counting_sort(MAX)
print(" ".join(map(str, B)))
### BUGGY CODE ###

N = int(input())

S = []

for _ in range(N):
    s = int(input())
    S.append(s)

max = 0
for i in range(s**N):
    L = [1]*N
    sum = 0
    for j in range(N):
        if (i>>j)&1:
            L[j] = 0
    for k in range(N):
        if L[k]==1:
            sum = sum + S[k]
    if max < sum and sum%10!=0:
        max = sum
print(max)

### FIXED CODE ###

N = int(input())

S = []

for _ in range(N):
    s = int(input())
    S.append(s)

max = sum(S)

if max%10!=0:
    print(max)
else:
    min = float('inf')
    for i in range(N):
        if S[i]<min and S[i]%10!=0:
            min = S[i]
    if min==float('inf'):
        print(0)
    else:
        print(max-min)
### BUGGY CODE ###

from fractions import gcd
import sys
n, m = map(int, input().split())
s = input()
t = input()
if s[0]==t[0]:
    g = gcd(n, m)
    x = g*(n//g)*(m//g)
    num_s, num_t = x//n, x//m
    for i in range(x):
        if (i-1)%num_s==0 and (i-1)%num_t==0:
            if s[(i-1)//num_s] == t[(i-1)//num_t]:
                continue
            else:
                print(-1)
                sys.exit()
    print(x)
else:
    print(-1)

### FIXED CODE ###

from fractions import gcd
import sys
n, m = map(int, input().split())
s = input()
t = input()
if s[0]==t[0]:
    g = gcd(n, m)
    x = g*(n//g)*(m//g)
    num_s, num_t = x//n, x//m
    for i in range(0, x, num_s):
        if i%num_t==0 and s[i//num_s]!=t[i//num_t]:
            print(-1)
            sys.exit()
    print(x)
else:
    print(-1)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(n+1):
    for j in range(n+1):
        if (n-i*r-j*g)%b==0 and n-i*r-j*g>=0:
            ans+=1
print(ans)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(n+1):
    for j in range(n+1):
        if (n-i*r-j*g)%b==0 and n-i*r-j*g>=0:
            ans+=1
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc176/submissions/16164430?lang=ja
import heapq

h, w = map(int, input().split())
sh, sw = map(lambda x: int(x) - 1, input().split())
gh, gw = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]

inf = 10 ** 10
D = [[inf] * w for i in range(h)]

D[sh][sw] = 0
Q = [(0, (sh, sw))]
heapq.heapify(Q)
while Q:
  _, (curr_h, curr_w) = heapq.heappop(Q)
  for di in range(-2, 3):
    for dj in range(-2, 3):
      next_h, next_w = curr_h + di, curr_w + dj
      if 0 <= next_h < h and 0 <= next_w < w and S[next_h][next_w] == ".":
        nex = int(abs(di) + abs(dj) != 1)
        if D[next_h][next_w] > D[curr_h][curr_w] + nex:
          D[next_h][next_w] = D[curr_h][curr_w] + nex
          heapq.heappush(Q, (D[next_h][next_w], (next_h, next_w)))
if D[gh][gw] >= inf:
  print(-1)
else:
  print(D[gh][gw])


### FIXED CODE ###

# https://atcoder.jp/contests/abc176/submissions/16164430?lang=ja
import heapq

h, w = map(int, input().split())
sh, sw = map(lambda x: int(x) - 1, input().split())
gh, gw = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]

inf = 10 ** 10
D = [[inf] * w for i in range(h)]

D[sh][sw] = 0
Q = [(0, (sh, sw))]
heapq.heapify(Q)
while Q:
  _, (curr_h, curr_w) = heapq.heappop(Q)
  for di in range(-2, 3):
    for dj in range(-2, 3):
      next_h, next_w = curr_h + di, curr_w + dj
      if 0 <= next_h < h and 0 <= next_w < w and S[next_h][next_w] == ".":
        nex = int(abs(di) + abs(dj) != 1)
        if D[next_h][next_w] > D[curr_h][curr_w] + nex:
          D[next_h][next_w] = D[curr_h][curr_w] + nex
          heapq.heappush(Q, (D[next_h][next_w], (next_h, next_w)))
if D[gh][gw] >= inf:
  print(-1)
else:
  print(D[gh][gw])
### BUGGY CODE ###

n, m, l = map(int, input().split())
abc_lst = [list(map(int, input().split())) for _ in range(m)]
q = int(input())
q_lst = [list(map(int, input().split())) for _ in range(q)]

edge_lst = []
for abc in abc_lst:
    a,b,c = abc
    if c <= l:
        edge_lst.append((a,b,c))
        edge_lst.append((b,a,c))
        
d_matrix = [[(-1, 10**10)] * (n+1) for _ in range(n+1)]
for i in range(n):
    d = [(-1, 10**10)] * (n+1)
    d[i+1] = (l, 0)
    while True:
        update = False
        for abc in edge_lst:
            a, b, c = abc
            if d[a][1] != 10**10:
                if d[a][0] < c:
                    cnt = d[a][1] + 1
                    f = l - c
                else:
                    cnt = d[a][1]
                    f = d[a][0] - c
                if d[b][1] == cnt:
                    if d[b][0] < f:
                        d[b] = (f, cnt)
                        update = True
                if d[b][1] > cnt:
                    d[b] = (f, cnt)
                    update = True
        if not update:
            break
        d_matrix[i+1] = d

for q in q_lst:
    s, t = q
    print(d_matrix[s][t][1]) if d_matrix[s][t][1] != 10**10 else print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M, L = map(int, input().split())
INF = float('inf')
VD = [[INF] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    VD[a][b] = c
    VD[b][a] = c
for i in range(N):
    VD[i][i] = 0
 
for k in range(N):
    for i in range(N):
        for j in range(N):
            if VD[i][j] > VD[i][k] + VD[k][j]:
                VD[i][j] = VD[i][k] + VD[k][j]
 
WD = [[INF] * N for _ in range(N)]
for i in range(N):
    WD[i][i] = 0
    for j in range(i+1,N):
        d = VD[i][j]
        if d <= L:
            WD[i][j] = 1
            WD[j][i] = 1
 
for k in range(N):
    for i in range(N):
        for j in range(N):
            if WD[i][j] > WD[i][k] + WD[k][j]:
                WD[i][j] = WD[i][k] + WD[k][j]
 
Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    print(WD[s-1][t-1]-1 if WD[s-1][t-1] < INF else -1)
### BUGGY CODE ###

#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]

    AB.sort(key=lambda a: (a[0]/a[1], a[0]), reverse=True)

    S = []
    for a, b in AB:
        n = H // a + 1
        h = H
        i = 1
        while n >= i:
            S.append((a*i, b*i))
            n -= i
            i <<= 1
        if n:
            S.append((a*n, b*n))

    N2 = len(S)
    def ubound(b, a, i):
        for j in range(i, N2):
            aj, bj = S[j]
            if a + aj >= H:
                return (b+bj, b + (H-a) * bj / aj)
            a += aj
            b += bj

        return (inf, inf)

    q = []
    u0, u1 = ubound(0, 0, 0)

    inf = float("inf")
    heappush(q, (u1, u0, 0, 0, 0))
    um = u0
    #print(AB)
    #print(H, S)
    while q:
        #print(q)
        uq0, uq1, aq, bq, i = heappop(q)

        if uq0 > um:
            break

        if i >= N2: continue

        ai, bi = S[i]
        if aq + ai < H:
            heappush(q, (uq0, uq1, aq + ai, bq + bi, i + 1))

        u0, u1 = ubound(bq, aq, i + 1)
        if u1 <= um:
            if u0 < um:
                um = u0
            heappush(q, (u1, u0, aq, bq, i + 1))

    print(um)



if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
import functools
INF = float("inf")

MOD = 1000000007  # type: int


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


def LCM(a, b):
    return a*b//GCD(a, b)


def solve(N: int, A: "List[int]"):

    # 最小公倍数
    lcm = 1
    for a in A:
        lcm = LCM(lcm, a)
    tot = 0

    @functools.lru_cache(maxsize=None)
    def f(a):
        return (lcm//a) % MOD
    tot = 0
    for a in A:
        tot += f(a)
    print(tot % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter
import math
MOD = 1000000007  # type: int


def factorial(n):
    prime_count = Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def div(a, b):
    return (a * power(b, MOD-2)) % MOD


def solve(N: int, A: "List[int]"):

    lcm = Counter()
    for a in A:
        c = factorial(a)
        for k in c:
            lcm[k] = max(c[k], lcm[k])
    # print(lcm)

    LCM = 1
    for k, v in lcm.items():
        LCM *= power(k, v)
        LCM %= MOD
    # print(LCM)

    tot = 0
    for a in A:
        tot += div(LCM, a)
    print(tot % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


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

N,M,P = map(int,input().split())
edge = [[]for i in range(N)]
cost = [-float('inf')]*N
cost[0] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    edge[a-1].append([b-1,c-P])

for i in range(N-1):
    for j in range(N):
        for b,c in edge[j]:
            cost[b] = max(cost[b],cost[j]+c)


for j in range(N):
    for b,c in edge[j]:
        if cost[b] < cost[j]+c:
            cost[b] = float('inf')


for i in range(N-1):
    for j in range(N):
        for b,c in edge[j]:
            cost[b] = max(cost[b],cost[j]+c)


if cost[-1] == float('inf'):
    print(-1)
else:
    print(max(cost[-1],0))

### FIXED CODE ###

N,M,P = map(int,input().split())
edge = []
cost = [-float('inf')]*N
cost[0] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,c-P])

for i in range(N-1):
    for a,b,c in edge:
        cost[b] = max(cost[b],cost[a]+c)


for a,b,c in edge:
    if cost[b] < cost[a]+c:
        cost[b] = float('inf')


for i in range(N-1):
    for a,b,c in edge:
        cost[b] = max(cost[b],cost[a]+c)

if cost[-1] == float('inf'):
    print(-1)
else:
    print(max(cost[-1],0))