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

import sys
input = sys.stdin.readline 
sys.setrecursionlimit(10 ** 6)

def main():
  N,M = map(int,input().split())
  path = [[] for i in range(N)]
  inf = 10 ** 6 * 2
  
  ans = [[None,inf] for i in range(N - 1)]
  
  for _ in range(M):
    a,b = map(int,input().split())
    a = a - 1
    b = b - 1
    path[a].append(b)
    path[b].append(a)
  
  def dfs(cur,par,con):
    if con == N + 1:
      return
    for chi in path[cur]:
      if chi == par:
        continue
      if con < ans[chi - 1][1]:
        ans[chi - 1][0] = cur
        ans[chi - 1][1] = con + 1
        dfs(chi,cur,con + 1)
  
  dfs(0,-1,0)
  
  if all([i[0] != None for i in ans]):
    print("Yes")
    for i in range(N - 1):
      print(ans[i][0] + 1)
  else:
    print("No")

if __name__=='__main__':
  main()

### FIXED CODE ###

from collections import deque

import sys
input = sys.stdin.readline 

N,M = map(int,input().split())
path = [[] for i in range(N)]
ans = [None for i in range(N)]
visited = [0 for i in range(N)]

for _ in range(M):
  a,b = map(int,input().split())
  a = a - 1
  b = b - 1
  path[a].append(b)
  path[b].append(a)

def bfs(path, root,visited):
  visited[root] = 1
  queue = deque([root])
  while queue:
    cur = queue.popleft()
    for chi in path[cur]:
      if visited[chi] == 1:
        continue
      else:
        ans[chi] = cur + 1
        visited[chi] = 1
        queue.append(chi)

  if all([i == 1 for i in visited]):
    return "Yes"
  else:
    return "No"
  
flag = bfs(path,0,visited)

print(flag)

if flag == "Yes":
  for i in range(1,N):
    print(ans[i])
### BUGGY CODE ###

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

dp = [[0] * 2 for i in range(n)]

ans = l[:]

for i in range(k):
    for j in range(n):
        tmp = ans[j] + 0.5
        dp[j][0] = (j+1 - tmp)
        dp[j][1] = (j+1 + tmp)

    ans = [0] * n

    for x in range(n):
        for y in range(n):
            if dp[y][0] <= x+1 <= dp[y][1]:
                ans[x] += 1

else:
    print(*ans)


### FIXED CODE ###

import numpy as np
from numba import njit

@njit #処理の並列化

def imos(n, a):
    
    l=np.zeros((n+1), dtype = np.int64)

    for i in range(n):
        ai = a[i] # 光の強さ_これにより照らせる範囲が決まる
        start = max(0, i - ai) #StartIndex_照らせる範囲
        end = min(n, i + ai + 1) #EndIndex + 1_照らせる範囲
        l[start] += 1 # 各々を'+1'と'-1'で表し...
        l[end] -= 1
    return np.cumsum(l)[:n] # 累積和をとる_cumulative sum

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

for _ in range(k):
    a = imos(n, a)
    if a.min() == n: # すべての要素が最大値'n'になるとbreak
        break

print(*a)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
cm = [[0 for j in range(w + 2)] for i in range(h + 2)]
que = deque([])
for i in range(1, h + 1):
    s = input()
    for j in range(1, w + 1):
        if s[j - 1] == ".":
            cm[i][j] = -1
        else:
            que.append(i)
            que.append(j)
ans = 0
while len(que) > 0:
    y = que.popleft()
    x = que.popleft()
    ans = cm[y][x] + 1
    if cm[y + 1][x] == -1:
        cm[y + 1][x] = ans
        que.append(y + 1)
        que.append(x)
    if cm[y - 1][x] == -1:
        cm[y - 1][x] = ans
        que.append(y - 1)
        que.append(x)
    if cm[y][x + 1] == -1:
        cm[y][x + 1] = ans
        que.append(y)
        que.append(x + 1)
    if cm[y][x - 1] == -1:
        cm[y][x - 1] = ans
        que.append(y)
        que.append(x - 1)
print(ans - 1)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
cm = [[0 for j in range(w + 2)] for i in range(h + 2)]
que = deque([])
for i in range(1, h + 1):
    s = input()
    for j in range(1, w + 1):
        if s[j - 1] == ".":
            cm[i][j] = -1
        else:
            que.append(i)
            que.append(j)
ans = 0
while len(que) > 0:
    y = que.popleft()
    x = que.popleft()
    ans = cm[y][x] + 1
    if cm[y + 1][x] == -1:
        cm[y + 1][x] = ans
        que.append(y + 1)
        que.append(x)
    if cm[y - 1][x] == -1:
        cm[y - 1][x] = ans
        que.append(y - 1)
        que.append(x)
    if cm[y][x + 1] == -1:
        cm[y][x + 1] = ans
        que.append(y)
        que.append(x + 1)
    if cm[y][x - 1] == -1:
        cm[y][x - 1] = ans
        que.append(y)
        que.append(x - 1)
print(ans - 1)
### BUGGY CODE ###

import numpy as np

N,M=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(N)]
A.sort()

A = np.array(A)

cnt = 0
for day in range(1,M+1):
    B = A[A[:,0]<=day,1]
    if B.size > 0:
        index = np.argmax(B)
        cnt += B[index]
        A = np.delete(A,index,0)
print(cnt)

### FIXED CODE ###

from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*10**5
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:M]:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)
### BUGGY CODE ###

n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
match={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
kind={}

for i in range(1,10):
    for aa in a:
        if i==aa:
            kind[match[i]]=i
m=len(kind)

inf=10**10

dp=[[-inf]*(n+1) for _ in range(m+1)]
cnt=[[0]*(n+1) for _ in range(m+1)]

dp[0][0]=0

a=sorted(list(kind.values()),reverse=True)
cost=[match[aa] for aa in a]
for i in range(m):
    cm=cost[i]

    for j in range(n+1):
        dp[i+1][j]=dp[i][j]

        if j>=cm and dp[i+1][j]<dp[i+1][j-cm]+1:
            dp[i+1][j]=dp[i+1][j-cm]+1

maxlen=dp[m][n]

def rec(x,i,s):
    if x==0 and len(s)==maxlen:
        print(s)
        exit(0)
    if i==m:
        return

    j=x//cost[i]
    while j>=0:
        rec(x-j*cost[i],i+1,s+''.join([str(a[i]) for _ in range(j)]))
        j-=1
    
rec(n,0,'')

### FIXED CODE ###

import math

n,_,*a=map(int,open(0).read().split())
match={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
a=sorted(a)

num=[0]*8

for d in a:
    num[match[d]]=d

dig=set(num)
dig.remove(0)
dig=sorted(list(dig),reverse=True)

dp=[-10**10]*(n+1)
dp[0]=0

for i in range(n+1):
    for d in dig:
        if i-match[d]<0:
            continue

        dp[i]=max(dp[i],dp[i-match[d]]+1)

ans=''

i=n
while i>0:
    for d in dig:
        if i-match[d]<0:
            continue
        if dp[i]==dp[i-match[d]]+1:
            ans=ans+str(d)
            break
    
    i-=match[d]

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

n = int(input())
a = []
for _ in range(n):
  i = int(input())
  if i in a:
    a.remove(i)
  else:
    a.append(i)
print(len(a))


### FIXED CODE ###

from collections import Counter
n = int(input())
a = []
for _ in range(n):
  i = int(input())
  a.append(i)
col = Counter(a)
ans = 0
for c in col.values():
	if c % 2 == 1: ans += 1
print(ans)
### BUGGY CODE ###

def gcd(a,b):
    i = 2
    temp = 1
    while(i <= b):
        while(a % i == 0 and b % i == 0):
            temp = temp * i
            a = a / i
            b = b / i
        if(i % 2 == 0):
            i = i + 1
        else:
            i = i + 2
    print temp

l = raw_input().split()
if(int(l[0]) > int(l[1])):
    gcd(int(l[0]),int(l[1]))
else:
    gcd(int(l[1]),int(l[0]))


### FIXED CODE ###

def gcd(a,b):
    if(b):
        return gcd(b,a%b)
    return a

l = raw_input().split()
if(int(l[0]) > int(l[1])):
    print gcd(int(l[0]),int(l[1]))
else:
    print gcd(int(l[1]),int(l[0]))
### BUGGY CODE ###

N = int(input())
As = list(map(int,input().split()))
c = int(As[0])
for x in range(N):
  if x == 0:
    continue
  c = int(c) * int(As[x])

if 1000000000000000001 <= c:
  print("-1")
else:
  print(c)


### FIXED CODE ###

N = int(input())
As = list(map(int,input().split()))
c = int(As[0])
i = 0
f = True
if 0 in As:
  print("0")
else:
  for x in As:
    if i == 0:
      i += 1
      continue
    c = c * x 
    if 1000000000000000001 <= c:
      print("-1")
      f = False
      break
  if f:
    print(c)
### BUGGY CODE ###

import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
L = [list(input().strip())  for _ in range(N)]
# S = input().strip

al = [[False for _ in range(M)] for _ in range(N)]
d = set()
for i in range(N):
    for j in range(M):
        if L[i][j] == "#":
            al[i][j] = True
            d.add((i, j))
            pass

for i in range(10000):
    if len(d) == 0:
        print(i - 1)
        exit()
    else:
        d2 = set()
        for x, y in d:
            if x - 1 >= 0 and al[x - 1][y] == False:
                al[x - 1][y] = True
                d2.add((x - 1, y))

            if x + 1 < N and al[x + 1][y] == False:
                al[x + 1][y] = True
                d2.add((x + 1, y))

            if y - 1 >= 0 and al[x][y - 1] == False:
                al[x][y - 1] = True
                d2.add((x, y - 1))

            if y + 1 < M and al[x][y + 1] == False:
                al[x][y + 1] = True
                d2.add((x, y + 1))

        d = d2

### FIXED CODE ###

import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
L = [list(input().strip())  for _ in range(N)]
# S = input().strip

al = [[False for _ in range(M)] for _ in range(N)]
d = []
for i in range(N):
    for j in range(M):
        if L[i][j] == "#":
            al[i][j] = True
            d.append((i, j))
            pass

for i in range(10000):
    if len(d) == 0:
        print(i - 1)
        exit()
    else:
        d2 = list()
        for x, y in d:
            if x - 1 >= 0 and al[x - 1][y] == False:
                al[x - 1][y] = True
                d2.append((x - 1, y))

            if x + 1 < N and al[x + 1][y] == False:
                al[x + 1][y] = True
                d2.append((x + 1, y))

            if y - 1 >= 0 and al[x][y - 1] == False:
                al[x][y - 1] = True
                d2.append((x, y - 1))

            if y + 1 < M and al[x][y + 1] == False:
                al[x][y + 1] = True
                d2.append((x, y + 1))

        d = d2
### BUGGY CODE ###

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

instr = input()
target = int(input())

# 部分文字列の一覧リストを作成
str_list = []
for i in range(len(instr)):

	for j in range(len(instr)+1):
		
		# targetよりも大きい文字数のものは処理しない
		if j-i > target:
			break
		
		if i < j:
			str_list.append(instr[i:j])
		j += 1
	i += 1

# 重複削除
str_list = list(set(str_list))
# 昇順ソート
str_list.sort()

print(str_list[target-1])

### FIXED CODE ###

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

instr = input()
target = int(input())

# 部分文字列の一覧リストを作成
str_list = []
for i in range(len(instr)):

	for j in range(i, len(instr)+1):
		
		# targetよりも大きい文字数のものは処理しない
		if j-i > target:
			break

		# 候補となる部分文字列の格納
		if i < j:
			str_list.append(instr[i:j])

		j += 1
	i += 1

# 重複削除
str_list = list(set(str_list))
# 昇順ソート
str_list.sort()

print(str_list[target-1])
### BUGGY CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

N += 2
X = [X[0] - 1] + X + [X[-1] + 1]
X = np.array(X, dtype=int)
# rdp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
rdp = np.zeros((N.bit_length() + 1, N), dtype=int)
rdp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length() + 1):
    rdp[d] = rdp[d - 1] + rdp[d - 1][np.arange(N) + rdp[d - 1]]

X = -X[::-1]
# ldp[d][i]: i番のホテルから(2^d)日で何個左までいけるか
ldp = np.zeros((N.bit_length() + 1, N), dtype=int)
ldp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length() + 1):
    ldp[d] = ldp[d - 1] + ldp[d - 1][np.arange(N) + ldp[d - 1]]


# print(rdp)
# print(ldp)


def solver(l, r):
    ret = 0
    while l < r:
        d = np.searchsorted(rdp[:, l], r - l)
        if rdp[d, l] == r - l:
            ret += 2 ** d
            break
        if d > 0:
            d -= 1
        ret += 2 ** d
        l += rdp[d, l]
    return ret


def solvel(l, r):
    r = N - r - 1
    l = N - l - 1
    ret = 0
    while l < r:
        d = np.searchsorted(ldp[:, l], r - l)
        if ldp[d, l] == r - l:
            ret += 2 ** d
            break
        if d > 0:
            d -= 1
        ret += 2 ** d
        l += ldp[d, l]
    return ret


# print(np.searchsorted([1, 2, 5, 8, 9], 3))
# print(np.searchsorted([1, 2, 5, 8, 9], 4))
# print(np.searchsorted([1, 2, 5, 8, 9], 5))
# print(np.searchsorted([1, 2, 5, 8, 9], 6))
# print(np.searchsorted([1, 2, 5, 8, 9], 7))
# print()

for a, b in AB:
    if a < b:
        r = solver(a, b)
    else:
        r = solvel(a, b)
    print(r)


### FIXED CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

N += 2
X = [X[0]] + X + [X[-1]]
X = np.array(X, dtype=int)
# dp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
dp = np.zeros((N.bit_length() + 1, N), dtype=int)
dp[0] = np.searchsorted(X, X + L, side="right") - 1
for d in range(1, N.bit_length() + 1):
    dp[d] = dp[d - 1][dp[d - 1]]
dp = dp.tolist()


def solve(l, r):
    ret = 0
    d = len(dp) - 1
    while l + 1 < r:
        while d > 0 and dp[d][l] >= r:
            d -= 1
        ret += 1 << d
        l = dp[d][l]
    if l < r:
        ret += 1
    return ret


ans = []
for a, b in AB:
    ans.append(solve(min(a, b), max(a, b)))
print(*ans, sep='\n')
### BUGGY CODE ###

k=int(input())
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans+=gcd(i,j,k)
print(ans)

### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    p = gcd(a,b)
    for c in range(1,k+1):
      ans += gcd(p,c)
print(ans)
### BUGGY CODE ###

s = input().strip()
K = int(input())
cnt = 0
x = ""
for i in range(len(s)):
    if i<len(s)-1 and (26-(ord(s[i])-ord("a")))%26 <= K-cnt:
        x += "a"
        cnt += (26-(ord(s[i])-ord("a")))%26
    elif i<len(s)-1:
        x += s[i]
    elif i==len(s)-1:
        k = ord(s[i])+(K-cnt)%26
        if k<=122:
            x += chr(k)
        else:
            x += chr(k-26)
print(x)

### FIXED CODE ###

s = input().strip()
K = int(input())
if K>len(s)*26:
    d = (K-len(s)*26)//26
    K = K-26*d
x = ""
for i in range(len(s)):
    if i<len(s)-1 and (26-(ord(s[i])-ord("a")))%26 <= K:
        x += "a"
        K -= (26-(ord(s[i])-ord("a")))%26
    elif i<len(s)-1:
        x += s[i]
    elif i==len(s)-1:
        k = ord(s[i])+K%26
        if k<=122:
            x += chr(k)
        else:
            x += chr(k-26)
print(x)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
r = ""
for i in set(range(N)):
  r+= str(A.index(i+1)+1)
  r+= " "
print(r)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(range(1,N+1,1))
C = zip(A,B)
D = sorted(C)
a, b = zip(*D)
print(" ".join(str(x) for x in b))
### BUGGY CODE ###

def inpl(): return [int(i) for i in input().split()]
N, K = inpl()
H = {0: 0}
for i in range(N):
    a, b= inpl()
    for ia, ib in H.copy().items():
        if ia | a <= K or (ia == 0 and a <= K):
            H[ia|a] = max(H.get(ia|a, 0), ib+b)
print(max(H.values()))

### FIXED CODE ###

import sys
N, K = map(int, input().split())
candi = []
p = 0
for i in range(30, -1, -1):
    if 2**i & K == 0:
        p += 2**i
        continue
    else:
        candi.append(p + 2**i)
candi.append(p)
AB = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0

for c in candi:
    cans = 0
    for a, b in AB:
        if a & c:
            continue
        cans += b
    ans = max(ans, cans)
print(ans)
### BUGGY CODE ###

import networkx as nx
n, m, *AB = map(int, open(0).read().split())
G = nx.Graph()
G.add_nodes_from(range(1, n+1))
for a, b in zip(AB[::2], AB[1::2]):
    G.add_edge(a, b)
print('Yes')
T = nx.bfs_tree(G, 1)
for i in range(2, n+1):
    print(*T.predecessors(i))

### FIXED CODE ###

from collections import deque
n, m, *AB = map(int, open(0).read().split())
graph = [[] for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

d = [0] * n
queue = deque([0])
while queue:
    current_node = queue.popleft()
    for next_node in graph[current_node]:
        if d[next_node] == 0:
            d[next_node] = current_node+1
            queue.append(next_node)
print('Yes')
print(*d[1:], sep='\n')
### BUGGY CODE ###

import sys

if __name__ == '__main__':
    n, m = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
    h = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
    matrix = {}

    for i in range(m):
        a, b = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
        a, b = a-1, b-1
        matrix[a] = matrix.get(a, []) + [b]
        matrix[b] = matrix.get(b, []) + [a]

    bads = []
    good = 0
    # 展望台iが良い展望台か
    for i in range(n):
        if i in set(bads):
            continue
        for t in matrix.get(i, []):
            if h[i] <= h[t]:
                break
            else:
                # 展望台tはもはや良い展望台でない
                bads += [t]
        else:
            good += 1
    print(good)

# matrixを疎行列にする
# 判定順をソートする


### FIXED CODE ###

import sys

if __name__ == '__main__':
    n, m = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
    h = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
    # matrix = {}
    # matrix = [[0 for i in range(n)] for j in range(n)]
    matrix = [[] for j in range(n)]

    for i in range(m):
        a, b = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
        a, b = a-1, b-1
        # matrix[a] = matrix.get(a, []) + [b]
        # matrix[b] = matrix.get(b, []) + [a]
        # matrix[a][b] = 1
        # matrix[b][a] = 1
        matrix[a].append(b)
        matrix[b].append(a)

    bads = {}
    good = 0
    # 展望台iが良い展望台か
    for i in range(n):
        if bads.get(i, 0) == 1:
            continue
        # for t in matrix.get(i, []):
        for t in matrix[i]:
            if h[i] <= h[t]:
                break
            else:
                # 展望台tはもはや良い展望台でない
                if t > i:
                    bads[t] = 1
        else:
            good += 1
    print(good)

# matrixを疎行列にする
# 判定順をソートする
### BUGGY CODE ###

def dp(n,W,w,p,cache):
  
  if n==0 or W==0:
    return 0
  elif (n,W) in cache.keys():
    return cache[(n,W)]
  else:
    if w[n-1]<=W:
      cache[(n,W)]=max(p[n-1]+dp(n-1,W-w[n-1],w,p,cache),dp(n-1,W,w,p,cache))
    else:
      cache[(n,W)]=dp(n-1,W,w,p,cache)
    return cache[(n,W)]
n,W=map(int,input().split())
weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p)
print(dp(n,W,weight,profit,dict()))

### FIXED CODE ###

n,W=map(int,input().split())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
  
def knapsack(wt, val, W, n):     
  
    # base conditions 
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    # choice diagram code 
    if wt[n-1] <= W: 
        t[n][W] = max(val[n-1] + knapsack(wt, val, W-wt[n-1], n-1),knapsack(wt, val, W, n-1)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack(wt, val, W, n-1) 
        return t[n][W] 

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p) 
print(knapsack(weight,profit, W, n))
### BUGGY CODE ###

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

def main():

    s = input()
    listS = list(s)
    n = len(listS)

    ans = 0
    count = 0

    for i in range(n):
        if listS[i] == 'A':
            for j in range(i, n):
                count += 1
                if listS[j] == 'Z':
                    if ans < count:
                        ans = count
            
            count = 0
            
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

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

def main():

    s = input()
    listS = list(s)
    n = len(listS)

    aIndex = 0
    zIndex = 0

    for i in range(n):
        if listS[i] == 'A':
            aIndex = i
            break

    for i in range(n):
        if listS[-(i + 1)] == 'Z':
            zIndex = n - i
            break

    ans = zIndex - aIndex

    print(ans)


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

class RangeMinimumQuery:
    def __init__(self, n, F=min, e=float("inf"), fill=None):
        self.n0 = 2**(n-1).bit_length()
        self.F = F
        self.e = e
        if fill is None:
            fill = e
        self.data = [fill]*(2*self.n0)

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.e
        while l < r:
            if r&1:
                r -= 1
                res = self.F(res, self.data[r-1])
            if l&1:
                res = self.F(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i:
            i = ~-i//2
            self.data[i] = self.F(self.data[2*i+1], self.data[2*i+2])

n,m,s = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    G[u].append([v, a, b])
    G[v].append([u, a, b])
cd = [list(map(int, input().split())) for i in range(n)]

from heapq import heappop, heappush
max_money = n*60
state = [RangeMinimumQuery(max_money+1) for i in range(n)]
s = min(s, max_money)
heap = [(0,(0,s),1)]

while heap:
    time, (cur, money), flag = heappop(heap)
    if state[cur].query(money, max_money+1) <= time:
        continue
    state[cur].update(money, time)
    if flag:
        n_money = money
        n_time = time
        f = False
        for i in range(10000):
            n_money += cd[cur][0]
            n_time += cd[cur][1]
            if n_money > max_money:
                n_money = max_money
                f = True
            heappush(heap, (n_time, (cur, n_money), 0))
            if f:
                break
    for to, a,b in G[cur]:
        if money < a or state[to].query(money-a, max_money+1) <= time+b:
            continue
        heappush(heap, (time+b, (to, money-a), 1))

for i in range(1, n):
    print(state[i].query(0, max_money+1))


### FIXED CODE ###

max_s = 2500

n,m,s = map(int, input().split())
s = min(s, max_s)
conv = lambda i,j : i*10000+j

G = [[] for i in range(conv(n-1, max_s)+1)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    for j in range(max_s+1):
        if j-a >= 0:
            G[conv(u,j)].append((conv(v,j-a), b))
            G[conv(v,j)].append((conv(u,j-a), b))

for i in range(n):
    c,d = map(int, input().split())
    for j in range(max_s+1):
        if j+c > max_s:
            break
        G[conv(i,j)].append((conv(i,j+c), d))

from heapq import heappush, heappop
def dijkstra(G, start):
    n = len(G)
    dist = [float("inf")]*n
    visited = set()
    heap = [(0, start)]

    while heap and len(visited) != n:
        d, cur = heappop(heap)
        if cur in visited:
            continue
        visited.add(cur)
        dist[cur] = d
        for to, cost in G[cur]:
            if to not in visited:
                heappush(heap, (d+cost, to))
    return dist

dist = dijkstra(G, conv(0, s))
for i in range(1,n):
    cost = min(dist[conv(i,0):conv(i,max_s)+1])
    print(cost)