Harryxun/stf_run huggingface dataset:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,x = inm()
blu = []
pt = 0
for i in range(n):
    b,l,u = inm()
    s = u*(x-b) + l*b
    v = s/x
    t = x
    heapq.heappush(blu, (-v,s,t,b,l,u))
    pt -= l*b

sum = 0
while len(blu)>0:
    mv,s,t,b,l,u = heapq.heappop(blu)
    nxtpt = pt + s
    ddprint("v {} b {} l {} u {} pt {} nx {} sum {}".format(v,b,l,u,pt,nxtpt,sum))
    if nxtpt < 0:
        pt = nxtpt
        sum += t
        continue
    elif nxtpt == 0:
        print(sum+t)
        exit()
    else:  # nxtpt > 0
        m = pt + l*b
        ddprint("m {}".format(m))
        if m>=0:
            t = b - (m)//l
        else:
            m = -m
            t = b + (m+u-1)//u
        s = -pt
        heapq.heappush(blu, (-s/t,s,t,b,l,u))


### FIXED CODE ###

import sys,heapq,time
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,x = inm()
blu = []
pt = 0
for i in range(n):
    b,l,u = inm()
    s = u*(x-b) + l*b
    v = s/x
    t = x
    heapq.heappush(blu, (-v,s,t,b,l,u,i))
    pt -= l*b

if pt==0:
    print(0)
    exit()

ans = []
reached = False
sum = 0
while len(blu)>0:
    mv,s,t,b,l,u,r = heapq.heappop(blu)
    nxtpt = pt + s
    ddprint("v {} s {} t {} b {} l {} u {} pt {} nx {} sum {}".format(-mv,s,t,b,l,u,pt,nxtpt,sum))
    if nxtpt < 0:
        ans.append((s,b,l,u))
        pt = nxtpt
        sum += t
        continue
    elif nxtpt == 0: # < (u if pt+l*b<0 else l):
        if not reached:
            ans.append((s,b,l,u))
            pt2 = pt + u*x - u*b + l*b
        sum += t
        break
    else:  # nxtpt > 0
        m = pt + l*b
        ddprint("m {}".format(m))
        if m>=0:
            t = (-pt+l-1)//l
        else:
            m = -m
            t = b + (m+u-1)//u
        if not reached:
            ans.append((s,b,l,u))
            pt2 = pt + u*x - u*b + l*b
            reached = True
        s = -pt
        ddprint("s/t {} s {} t {}".format(s/t,s,t))
        heapq.heappush(blu, (-s/t,s,t,b,l,u,-1))

sum2 = x * (len(ans)-1)
for z in ans[:-1]:
    s,b,l,u = z
    pt = pt2 - s
    m = pt + l*b
    if m>=0:
        t = (-pt+l-1)//l
    else:
        t = b+(-m+u-1)//u
    if sum2+t < sum:
        sum = sum2+t
print(sum)
def is_prime(x: int)->None:
    # 解説見た
    if x <= 1:
        return True
    i: int = 2
    while i * i <= x:
        if x % i == 0:
            return True
        i += 1
    return False


def main()->None:
    X: int = int(input())
    p: int = X
    while is_prime(p):
        p += 1
    print(p)

if __name__ == "__main__":
    main()

### FIXED CODE ###


def is_prime(x):
    # 解説見た
    if x <= 1:
        return True
    i = 2
    while i * i <= x:
        if x % i == 0:
            return True
        i += 1
    return False


def main():
    X = int(input())
    p = X
    while is_prime(p):
        p += 1
    print(p)

if __name__ == "__main__":
    main()
import numpy as np

def chk_route(c,s,T):
    global H,W,R
    mx = H*W
    #print(c)
    #print(T)
    flg = 0
    T[c[0]][c[1]]=s
    if R[c[0]][c[1]] > s:
        R[c[0]][c[1]] = s

    if c[0] != H-1:
        #if T[c[0]+1][c[1]]!=1 and T[c[0]+1][c[1]]!=s-1 and T[c[0]+1][c[1]]!=2:
        if T[c[0]+1][c[1]]==0:
            flg=1
            B=T.copy()
            chk_route([c[0]+1,c[1]],s+1,B)
    if c[0] != 0:
        #if T[c[0]-1][c[1]]!=1 and T[c[0]-1][c[1]]!=s-1 and T[c[0]-1][c[1]]!=2:
        if T[c[0]-1][c[1]]==0:
            flg=1
            B=T.copy()
            chk_route([c[0]-1,c[1]],s+1,B)
    if c[1] != W-1:
        #if T[c[0]][c[1]+1]!=1 and T[c[0]][c[1]+1]!=s-1 and T[c[0]][c[1]+1]!=2:
        if T[c[0]][c[1]+1]==0:
            flg=1
            B=T.copy()
            chk_route([c[0],c[1]+1],s+1,B)
    if c[1] != 0:
        #if T[c[0]][c[1]-1]!=1 and T[c[0]][c[1]-1]!=s-1 and T[c[0]][c[1]-1]!=2:
        if T[c[0]][c[1]-1]==0:
            flg=1
            B=T.copy()
            chk_route([c[0],c[1]-1],s+1,B)

    if flg == 0:
        #print(T)
        #r=np.count_nonzero(T==2)
        if R[c[0]][c[1]] > s:
            R[c[0]][c[1]] = s
        #return s
    if s==2: pass #return mx
        #T=np.copy(B)
H,W= [int(x) for x in input().split()]
n=[]
#T = [[0] * W for i in range(H)]
T=np.zeros((H,W),dtype=int)
MX = H*W
R=np.full((H,W),MX,dtype = int)
#R = [[15] * W for i in range(H)]
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#print(T)
d=0
for i in range(H):
    for j in range(W):

        if T[i][j] =='1':continue

        c=[i,j]
        B=T.copy()
        R=np.full((H,W),MX,dtype = int)
        chk_route(c,int(2),B)

        d = max(d,np.max(R[np.where(R<MX)]))

        #b= b[np.where(b[:,22].astype(float) > 0)]
print(d-2)
#print(mx)



### FIXED CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
#T=[]
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        #c.append(j)
        
        #t=len(c)
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        #print(T)
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype=int)
        
print(d-1)
X,Y = input().split()
if X==Y:
    print("=")
elif(X>Y:
    print(">"))
else:
    print("<")

### FIXED CODE ###

X,Y = input().split()
if X==Y:
    print("=")
elif(X>Y):
    print(">")
else:
    print("<")
n = int(input())
b = [int(i) for i in input().split()]

a =[b[0]]

for x in range(n-1):
  s = min(b[x],b[x+1])
  a.append(s)
  
a.append(b[-1])

print(sum(a))

### FIXED CODE ###

#nは数列Aの長さ　Bの長さはn-1
n = int(input())
bn = list(map(int,input().split()))

an =[bn[0]]


for x in range(n-2):
    if bn[x+1] >= bn[x] :
        an.append(bn[x])
    else:
        an.append(bn[x+1])

an.append(bn[-1])

print(sum(an))
s = int(input())
ans = "Good"
for i in range(10):
  k = str(i)+str(i)
  if(k in s):
    ans = "Bad"
    break
print(ans)

### FIXED CODE ###

s = str(input())
ans = "Good"
for i in range(10):
  k = str(i)+str(i)
  if(k in s):
    ans = "Bad"
    break
print(ans)
N,Y = map(int,input().split())
for a in range(N):
    for b in range(N):
        10000*a+5000*b+1000*(N-a-b) == Y
        print(a,b,N-a-b)
    	break
	break

### FIXED CODE ###

N,Y = map(int,input().split())
for i in range(N+1):
    for n in range(N-i+1):
        if 10000*i+5000*n+1000*(N-i-n) == Y:
            print(i,n,N-i-n)
            break
    else:
        continue
    break
else:
    print(-1,-1,-1)
N = int(input())
A_arr = list(map(int, input().split()))

A_arr = sorted(A_arr, reverse=True)
two_arr = []
for i in range(1,31):
    two_arr.append(2**i)

count = 0
while len(A_arr) != 0:
    for j in range(30):
        if A_arr[0] > two_arr[j]:
            pass
        else:
            v_pair = two_arr[j] - A_arr[0]
            break
    if v_pair in A_arr:
        A_arr.remove(v_pair)
        count += 1
    else:
        pass
    A_arr.pop(0)

print(count)

### FIXED CODE ###

from collections import Counter
N = int(input())
A_arr = list(map(int, input().split()))

A_arr = sorted(A_arr, reverse=True)
C_arr = Counter(A_arr)

count = 0
for i in range(N):
    v_max = A_arr[i]
    if C_arr[v_max] == 0:
        continue
    C_arr[v_max] -= 1
    v_pair = 2**v_max.bit_length() - v_max
    if C_arr[v_pair] > 0:
        C_arr[v_pair] -= 1
        count += 1
    else:
        pass

print(count)
n, m = tuple(map(int, input().split()))
list = list(map(int, input().split()))
list = sorted(list)
list2 = list.copy()

list.pop(-1)
list2.pop(0)

diff = []
for i in range(len(list)):
    diff.append(list[i] - list2[i])

abs_diff = []
for i in range(len(diff)):
    abs_diff.append(abs(diff[i]))

abs_diff = sorted(abs_diff)

if abs_diff != []:
    for _ in range(n - 1):
        abs_diff.pop(abs_diff.index(max(abs_diff)))

print(sum(abs_diff))

### FIXED CODE ###

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

diff = []

for i in range(len(x) - 1):
    diff.append(x[i + 1] - x[i])

diff = sorted(diff)

diff_sum = 0
diff_len = m - 1

for i in range(diff_len - (n - 1)):
    diff_sum += diff[i]

print(diff_sum)
n=int(input())
node=[-1 for i in range(n)]
g=[[]for i in range(n)]
def color(par,i,ini):
  if node[i]>-1:
    return
  else:
    if par==-1:
      node[i]=0
    else:
      node[i]=abs(node[par]-ini)
    for j in range(len(g[i])):
      color(i,g[i][j][0],g[i][j][1])
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  w%=2
  g[u].append([v,w])
  g[v].append([u,w])

for i in range(n):
  color(-1,i,0)
for i in range(n):
  if node[i]==-1:
    node[i]=0
  print(node[i])

### FIXED CODE ###

n=int(input())
node=[-1 for i in range(n)]
g=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  w%=2
  g[u].append([v,w])
  g[v].append([u,w])
queue=[0]
node[0]=0
while len(queue)>0:
  t=queue.pop()
  for v,w in g[t]:
    if node[v]>-1:
      continue
    node[v]=node[t]^w
    queue.append(v)
for i in range(n):
  print(node[i])
s= input()
if s[0]=='Y' and  s[1]=='A' and s[2]=='K' and s[3]=='I':
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s= input()
if len(s)>3 and s[0]=='Y' and  s[1]=='A' and s[2]=='K' and s[3]=='I':
    print("Yes")
else:
    print("No")
# -*- coding: utf-8 -*-


N,K=map(int, input().split())
H=list(map(int, input().split()))
G=[0]
G.extend(H[:])

dp=[[0]*(N+1) for i in range(N-K+1)]
dp[1][1]=G[1]
for jtemp in range(N-1):
    j=jtemp+2
    dp[1][j]=G[j]#min(dp[1][j-1],G[j])
if K<N-1:
    for itemp in range(N-K-1):
        i=itemp+2
        for jtemp in range(N-(i-1)):
            j=jtemp+i
            temp=int(N*1e9)
            
            for ktemp in range(j-(i-1)):
                k=ktemp+i-1
                val=G[j]-G[k]
                if val<0:
                    val=0
                if temp>dp[i-1][k]+val:
                    temp=dp[i-1][k]+val
            dp[i][j]=temp
    temp=dp[N-K][-1]
    for jtemp in range(N):
        j=jtemp+1
        if temp>dp[N-K][j] and dp[N-K][j]!=0:
            temp=dp[N-K][j]
elif K==1:
    temp=min(H[:])
else:
    temp=0
print(temp)

### FIXED CODE ###

# -*- coding: utf-8 -*-


N,K=map(int, input().split())
H=list(map(int, input().split()))
G=[0]
G.extend(H[:])

dp=[[0]*(N+1) for i in range(N-K+1)]


tempa=0
if K<N-1:
    for jtemp in range(N):
        j=jtemp+1
        dp[1][j]=G[j]#min(dp[1][j-1],G[j])
    for itemp in range(N-K-1):
        i=itemp+2
        for jtemp in range(N-(i-1)):
            j=jtemp+i
            temp=int(N*1e9)
            
            for ktemp in range(j-(i-1)):
                k=ktemp+i-1
                val=G[j]-G[k]
                if val<0:
                    val=0
                if temp>dp[i-1][k]+val:
                    temp=dp[i-1][k]+val
            dp[i][j]=temp
    tempa=dp[N-K][-1]
    for jtemp in range(N):
        j=jtemp+1
        if tempa>dp[N-K][j] and dp[N-K][j]!=0:
            tempa=dp[N-K][j]
elif N-K==1:
    tempa=min(H[:])
else:
    tempa=0
print(tempa)
from math import factorial

n, a, b = map(int, input().split(" "));
v = list(map(int, input().split(" ")))


def product(iterable):
    prod = 1
    for n in iterable:
        prod *= n
    return prod

def npr(n, r):
    return product(range(n - r + 1, n + 1))

def ncr(n, r):
    if r > n // 2:
        r = n - r
    return npr(n, r) // factorial(r)

v.sort();
revv=list(reversed(v))
print(sum(v[-a:])/a)

revpos=revv.index(v[-a]);
num=v.count(v[-a]);
ans=0;
for i in range(a-revpos, b-revpos+1):
    ans+=ncr(num, i);
print(ans);


### FIXED CODE ###

a, b = map(int, input().split(" "));
print( (a+b) % 24);
import sys

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

flag = 0

if((e-a)=<k):
 print("Yay!")
 flag = 1
if(flag == 1):
  print(":(")
 

### FIXED CODE ###

import sys

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

flag = 0

if((b-a)>k or (c-a)>k or (d-a)>k or (e-a)>k or (c-b)>k or (d-b)>k or (e-b)>k or (d-c)>k or (e-c)>k or (e-d)>k):
  print(":(")
else:
  print("Yay!")
A,B=map(int,input().split())
print((B*100)*A//100)

### FIXED CODE ###

def main():
    a,b=map(float,input().split())
    a=int(a)
    print(int((b*100+0.1)//1)*a//100)
main()
N = int(input()) #5
K = int(input()) #3
X = int(input())
Y = int(input())

total = 0
for a in range(1, N+1): #6 , 1, 2, 3, 4, 5
	if a < K:
		total += X
    else:
		total += Y

print(total)


### FIXED CODE ###

N = int(input()) #5
K = int(input()) #3
X = int(input())
Y = int(input())

total = 0
for a in range(1, N+1): #6 , 1, 2, 3, 4, 5
    if a <= K:
        total += X
    else:
        total += Y

print(total)
input = sys.stdin.readline
n,c,k = map(int,input().split())
A = [int(input()) for i in range(n)]
a = sorted(A)
ans = 0
time = 0.1 
num = 0
for i in range(n):
    if ans == 0:
        ans +=1
        time = a[0] -0.1
        num +=1
    elif ans != 0 and a[i] < time +k and num < c :
        num +=1
    elif  ans != 0 and (c <=num  or  time +k <=a[i]):
      
        time = a[i] -0.1
        num = 1
        ans +=1
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
# sys.stdin.readline()
import numpy as np
import sys
import math
input = sys.stdin.readline
n,c,k = map(int,input().split())
A = [int(input()) for i in range(n)]
a = sorted(A)
ans = 0
time = 0.1 
num = 0
for i in range(n):
    if ans == 0:
        ans +=1
        time = a[0] 
        num +=1
    elif ans != 0 and a[i] <= time +k and num < c :
        num +=1
    elif  ans != 0 and (c <=num  or  time +k <=a[i]):
      
        time = a[i] 
        num = 1
        ans +=1
print(ans)
A,B,K=map(int,input().split())
l=[]
for i in range(101):
    if A%i==0 and B%i==0:
        l.append(i)
print(l[i-1])

### FIXED CODE ###

A,B,K=map(int,input().split())
l=[]
for i in range(1,101):
    if A%i==0 and B%i==0:
        l.append(i)
print(l[-K])
x=input()
x=x**3
print(x)

### FIXED CODE ###

x=int(input())
x=x**3
print(x)
from collections import deque

N = int(input())
A = list(map(int, input().split()))
A.sort()
d = deque(A)
if A[0] <= 0 and A[-1] > 0:
    print(sum(map(abs, A)))
    while len(d) > 2:
        while d[1] < 0 and len(d)>2:
            print(list(d))
            x = d.pop()
            y = d.popleft()
            print(x, y)
            d.append(x - y)
        x = d.popleft()
        y = d.pop()
        print(x, y)
        d.appendleft(x - y)
    if len(d) >= 2:
        print(d[1], d[0])

elif A[0] > 0:
    print(sum(A) - 2 * A[0])
    x = d.popleft()
    y = d.pop()
    print(x, y)
    d.appendleft(x - y)
    while len(d) > 2:
        x = d.popleft()
        y = d.pop()
        print(x, y)
        d.appendleft(x - y)
    if len(d) >= 2:
        print(d[1], d[0])
else:
    print(-sum(A) + 2 * A[-1])
    x = d.pop()
    y = d.popleft()
    print(x, y)
    d.append(x - y)
    while len(d) > 2:
        while d[1] < 0 and len(d) > 2:
            x = d.pop()
            y = d.popleft()
            print(x, y)
            d.append(x - y)
        x = d.pop()
        y = d.popleft()
        print(x, y)
        d.appendleft(x - y)
    if len(d) >= 2:
        print(d[1], d[0])


### FIXED CODE ###

from collections import deque

N = int(input())
A = list(map(int, input().split()))
A.sort()
d = deque(A)
if A[0] <= 0 and A[-1] >= 0:
    print(sum(map(abs, A)))
    while len(d) > 2:
        while d[1] < 0:
            x = d.pop()
            y = d.popleft()
            print(x, y)
            d.append(x - y)
        x = d.popleft()
        y = d.pop()
        if d:
            print(x, y)
        else:
            print(y, x)
        d.appendleft(x - y)
    if len(d) >= 2:
        print(d[1], d[0])

elif A[0] > 0:
    print(sum(A) - 2 * A[0])
    x = d.popleft()
    y = d.pop()
    if not d:
        print(y, x)
    else:
        print(x, y)
    d.appendleft(x - y)
    while len(d) > 2:
        x = d.popleft()
        y = d.pop()
        print(x, y)
        d.appendleft(x - y)
    if len(d) >= 2:
        print(d[1], d[0])
else:
    print(-sum(A) + 2 * A[-1])
    x = d.pop()
    y = d.popleft()
    print(x, y)
    d.append(x - y)
    while len(d) > 2:
        while d[1] < 0 and len(d) > 2:
            x = d.pop()
            y = d.popleft()
            print(x, y)
            d.append(x - y)
        x = d.pop()
        y = d.popleft()
        print(x, y)
        d.appendleft(x - y)
    if len(d) >= 2:
        print(d[1], d[0])
import itertools

N_MAX = 100000
INF = float('inf')

n = int(input().rstrip())

dp = [INF for _ in range(N_MAX)]
dp[0] = 0
dp[1] = 1
dp[6] = 1
dp[9] = 1

for i in range(1, n + 1):

    # [1, 6, 36, ...]
    for j in itertools.takewhile(lambda x: x < N_MAX,
                                 (6 ** c for c in itertools.count())):
        dp[i] = min(dp[i], dp[i - j] + 1)

    # [1, 9, 81, ...]s
    for j in itertools.takewhile(lambda x: x < N_MAX,
                                 (9 ** c for c in itertools.count())):
        dp[i] = min(dp[i], dp[i - j] + 1)

print(dp[n])


### FIXED CODE ###

def main():
    N = int(input())

    dp = [999999999999 for _ in range(N + 1)]
    dp[0] = 0

    for n in range(1, N + 1):
        # 1 yen
        dp[n] = min(dp[n], dp[n - 1] + 1)

        # 6 yen
        i = 6
        while i <= n:
            dp[n] = min(dp[n], dp[n - i] + 1)
            i *= 6

        # 9 yen
        i = 9
        while i <= n:
            dp[n] = min(dp[n], dp[n - i] + 1)
            i *= 9

    print(dp[N])


main()
# -*- coding:utf-8 -*-

result = list()

def operation(command):
    if command[0] == "insert":
        result.insert(0, int(command[1]))
    elif command[0] == "delete":
        result.remove(int(command[1]))
    elif command[0] == "deleteFirst":
        result.pop(0)
    elif command[0] == "deleteLast":
        result.pop()

n = int(input())
for i in range(n):
    command = input().split()
    operation(command)
print(*result)

### FIXED CODE ###

# -*- coding:utf-8 -*-

from collections import deque

result = deque()

def operation(command):
    if command[0] == "insert":
        result.appendleft(command[1])
    elif command[0] == "delete":
        if command[1] in result:
            result.remove(command[1])
    elif command[0] == "deleteFirst":
        result.popleft()
    elif command[0] == "deleteLast":
        result.pop()

n = int(input())
for i in range(n):
    command = input().split()
    operation(command)
print(*result)
a = int(input())
b = int(input())

if a*b % 2 == 0:
    print("Even")
else:
    print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())

if a*b % 2 == 0:
    print("Even")
else:
    print("Odd")
N,K = map(int,input().split(" "))
trickSum = 0
result = list()
while True :
    d = input()
    if d == "":
        break
    result = result + (list(map(int, input().split(" "))))
print(N - len(set(result)))

### FIXED CODE ###

N,K = map(int,input().split(" "))
trickSum = 0
result = list()
for i in range(K):
    d = input()
    result = result + (list(map(int, input().split(" "))))
print(N - len(set(result)))
def csum(c):
  r = 0
  for index, item in enumerate(c):
    r += index * item
  return r

n = int(input())
l= list(map(int,input().split()))
c = [0] * 10001
for i in l:
  c[i] += 1
n = int(input())
s = csum(c)
for i in range(0, n):
  be,af = map(int,input().split())
  s -= be * c[be]
  s += af * c[be]
  c[af] += c[be]
  c[be] = 0
  print(s)

### FIXED CODE ###

N = int(input())
A= list(map(int,input().split()))
Q = int(input())
heavy = [0] * (10 ** 5 + 1)
for i in A:
  heavy[i] += 1
s = sum(A)
for i in range(Q):
  be,af = map(int,input().split())
  s -= be * heavy[be]
  s += af * heavy[be]
  heavy[af] += heavy[be]
  heavy[be] = 0
  print(s)
import heapq

N, M, S = map(int, input().split())
Cost = [[[-1, -1] for _ in range(N)] for _ in range(N)]
Change = [[0]*2 for _ in range(N)]
A_m = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    A_m = max(A_m, a)
    Cost[u-1][v-1][0] = a
    Cost[u-1][v-1][1] = b
    Cost[v-1][u-1][0] = a
    Cost[v-1][u-1][1] = b
for i in range(N):
    c, d = map(int, input().split())
    Change[i][0] = c
    Change[i][1] = d
if S > 2500:
    S = 2500

def dijkstra(N, start, Cost, Change):
    minHeap = []
    used = [[10**12]*(A_m*N + 1) for _ in range(N)]
    used[start][S] = 0
    heapq.heappush(minHeap, (0, S, start))
    while minHeap:
        (c, hold, current) = heapq.heappop(minHeap)
        for road in range(N):
            if Cost[current][road][0] != -1:
                if hold >= Cost[current][road][0]:
                    if used[road][hold - Cost[current][road][0]] > c + Cost[current][road][1]:
                        used[road][hold - Cost[current][road][0]] = c + Cost[current][road][1]
                        heapq.heappush(minHeap, (c + Cost[current][road][1], hold - Cost[current][road][0], road))
        if hold + Change[current][0] <= A_m*N:
            if used[current][hold + Change[current][0]] > c + Change[current][1]:
                heapq.heappush(minHeap, (c + Change[current][1], hold + Change[current][0], current))
    return used

T = dijkstra(N, 0, Cost, Change)
for i in T[1:]:
    print(min(i))


### FIXED CODE ###

import heapq

N, M, S = map(int, input().split())
Cost = [[] for _ in range(N)]
Change = [[0]*2 for _ in range(N)]
A_m = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    A_m = max(A_m, a)
    Cost[u-1].append([v-1, a, b])
    Cost[v-1].append([u-1, a, b])
for i in range(N):
    c, d = map(int, input().split())
    Change[i][0] = c
    Change[i][1] = d
if S > A_m*N:
    S = A_m*N

def dijkstra(N, start, Cost, Change):
    rich = [[] for _ in range(N+1)]
    Ans = [10**18]*N
    Ans[0] = 0
    minHeap = []
    used = [[10**18]*(A_m*N + 1) for _ in range(N)]
    used[start][S] = 0
    heapq.heappush(minHeap, (0, S, start))
    while minHeap:
        (c, hold, current) = heapq.heappop(minHeap)
        if rich[current] and rich[current][-1] >= hold:
            continue
        rich[current].append(hold)
        j = 1
        for i in range(N):
            if Ans[i] > c:
                j = 0
                break
        if j == 1:
            break
        for P in Cost[current]:
            road, a, b = P
            if hold >= a:
                if used[road][hold - a] > c + b:
                    used[road][hold - a] = c + b
                    heapq.heappush(minHeap, (c + b, hold - a, road))
                if Ans[road] > c + b:
                    Ans[road] = c + b
        if hold + Change[current][0] <= A_m*N:
            if used[current][hold + Change[current][0]] > c + Change[current][1]:
                heapq.heappush(minHeap, (c + Change[current][1], hold + Change[current][0], current))
    return Ans

T = dijkstra(N, 0, Cost, Change)
for i in T[1:]:
    print(i)
n, m, X, Y = map(int, input().split())
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]

x.append(X)
y.append(Y)

if max(x) < min(y):
    print("No War")
else :
    print("War")

### FIXED CODE ###

a, b, c = map(int, input().split())
array = [a, b, c]
array.sort()
print(array[-1] * 10 + array[0] + array[1])