Harryxun/stf_run huggingface dataset:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    n=int(readline())
    ss=readline().rstrip()
    j=len(ss)
    ans=0
    for i in range(len(ss)):
        if ss[i]=="W":
            j-=1
            if j >= 0:
                while ss[j]!="R":
                    j-=1
            if j > i:
                ans+=1
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

### FIXED CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    n=int(readline())
    ss=readline().rstrip()
    j=len(ss)
    ans=0
    if j==1:
        print(0)
        return
    for i in range(len(ss)):
        if ss[i]=="W":
            j-=1
            if j >= 0:
                while ss[j]!="R":
                    j-=1
                    if j < 0:
                        break
            if j > i:
                ans+=1
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------
def dev(n):
    if n = 1:
        retuen 1
    else:
        retuen 1 + dev(n//2) * 2

print(dev(h))


### FIXED CODE ###

h = int(input())

def dev_(n):
    if n == 1:
        return 1
    else:
        return 1 + dev_(n//2) * 2

print(dev_(h))
def main():
	N = int(input())
	a = input()
    
	W = [0]
	E = [0]
	for i in range(N):
		if a[i] == 'W':
			W[i+1] = W[i] + 1
			E[i+1] = E[i]
		else:
			W[i+1] = W[i]
			E[i+1] = E[i] + 1
	E_max = E[-1]
	n_min = N
	for i in range(N):
		t = W[i] + E_max - E[i+1]
		if t < n_min:
			n_min = t
	print (n_min)
main()

### FIXED CODE ###

def main():
	N = int(input())
	a = input()
    
	W = [0]*(N+1)
	E = [0]*(N+1)
	for i in range(N):
		if a[i] == 'W':
			W[i+1] = W[i] + 1
			E[i+1] = E[i]
		else:
			W[i+1] = W[i]
			E[i+1] = E[i] + 1
	E_max = E[-1]
	n_min = N
	for i in range(N):
		t = W[i] + E_max - E[i+1]
		if t < n_min:
			n_min = t
	print (n_min)
main()
#!/usr/bin/python3
# -*- coding: utf-8 -*-
s = input()
t = input()
min_count = 1000
for i in range(len(s) - len(t) + ):
    count = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            count += 1
    min_count = min(count, min_count)
    if min_count == 0:
        break
print(min_count)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
s = input()
t = input()
min_count = 1000
for i in range(len(s) - len(t) + 1):
    count = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            count += 1
    min_count = min(count, min_count)
    if min_count == 0:
        break
print(min_count)
a, b, c, d = map(int,input().split())


if -(-c // b) <= -(-a // d):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s, w = map(int,input().split())

if s <= w:
    print('unsafe')
else:
    print('safe')
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
AB = I[1:]
G = collections.defaultdict(set)
for a, b in zip(AB[::2], AB[1::2]):
    G[a].add(b)
    G[b].add(a)
color = [None] * (N + 1)


def dfs(G, v, cur):
    color[v] = cur
    for w in G[v]:
        if color[w] is None:
            dfs(G, w, 1 - cur)


dfs(G, 1, 0)
c=collections.Counter(color[1:])
cand1 = set(range(1, N + 1, 3))
cand2 = set(range(2, N + 1, 3))
cand3 = set(range(3, N + 1, 3))

i0, i1 = 0, 1
if c[0] > c[1]:
    i0, i1 = 1, 0

ans = [None] * (N + 1)
if c[i0] <= len(cand3):
    for i in range(1, N + 1):
        if color[i]==i0:
            ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            elif cand2:
                ans[i] = cand2.pop()
            else:
                ans[i] = cand3.pop()
else:
    for i in range(1, N + 1):
        if color[i]==i0:
            if cand1:
                ans[i] = cand1.pop()
            else:
                ans[i] = cand3.pop()
        else:
            if cand2:
                ans[i] = cand2.pop()
            else:
                ans[i] = cand3.pop()
print(*ans[1:])


### FIXED CODE ###

import collections
import sys
sys.setrecursionlimit(2*10**5)
I = [int(_) for _ in open(0).read().split()]
N = I[0]
AB = I[1:]
G = collections.defaultdict(set)
for a, b in zip(AB[::2], AB[1::2]):
    G[a].add(b)
    G[b].add(a)
color = [None] * (N + 1)


def dfs(G, v, cur):
    color[v] = cur
    for w in G[v]:
        if color[w] is None:
            dfs(G, w, 1 - cur)


dfs(G, 1, 0)
c=collections.Counter(color[1:])
cand1 = set(range(1, N + 1, 3))
cand2 = set(range(2, N + 1, 3))
cand3 = set(range(3, N + 1, 3))

i0, i1 = 0, 1
if c[0] > c[1]:
    i0, i1 = 1, 0

ans = [None] * (N + 1)
if c[i0] <= len(cand3):
    for i in range(1, N + 1):
        if color[i]==i0:
            ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            elif cand2:
                ans[i] = cand2.pop()
            elif cand3:
                ans[i] = cand3.pop()
else:
    for i in range(1, N + 1):
        if color[i] == i0:
            if cand2:
                ans[i] = cand2.pop()
            elif cand3:
                ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            elif cand3:
                ans[i] = cand3.pop()
print(*ans[1:])
a, b = map(int, input().split(' '))
print('{} {}'.format(a*b, 2(a+b)))

### FIXED CODE ###

a, b = map(int, input().split(' '))
print('{} {}'.format(a*b, 2*(a+b)))
import sys
import os
f = open('../../input.txt', 'r')
sys.stdin = f

from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

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

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

for i in range(m):
    x,y = map(int, input().split())
    xy_dict[x].append(y)

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

def get_longest(x):
    global dp

    if( dp[x] >= 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

ans = 0
for i in range(1,n+1):
    ans = max(ans, get_longest(i))

print(ans)


### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

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

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

for i in range(m):
    x,y = map(int, input().split())
    xy_dict[x].append(y)

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

def get_longest(x):
    global dp

    if( dp[x] >= 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

ans = 0
for i in range(1,n+1):
    ans = max(ans, get_longest(i))

print(ans)
x, y, a, b, c = map(int, input().split())
p = sorted(map(int, input().split()))
q = sorted(map(int, input().split()))
r = sorted(map(int, input().split()), reverse=True)
pi = len(p) - x
qi = len(q) - y
ri = 0
for _ in range(len(r)):
    if r[ri] <= min(p[pi], q[qi]):
        break
    else:
        if pi < len(p) and qi < len(q):
            if p[pi] < q[qi]:
                p[pi] = r[ri]
                pi += 1
                ri += 1
                continue
            else:
                q[qi] = r[ri]
                qi += 1
                ri += 1
                continue
        elif pi >= len(p) and qi < len(q):
            if q[qi] < r[ri]:
                q[qi] = r[ri]
                qi += 1
                ri += 1
                continue
        elif pi < len(p) and qi >= len(q):
            if p[pi] < r[ri]:
                p[pi] = r[ri]
                pi += 1
                ri += 1
                continue
        else:
            break
print(sum(p[-x:]) + sum(q[-y:]))


### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = sorted(map(int, input().split()))
q = sorted(map(int, input().split()))
r = sorted(map(int, input().split()), reverse=True)
pi = len(p) - x
qi = len(q) - y
ri = 0
for _ in range(len(r)):
    if r[ri] <= min(p[min(pi, len(p)-1)], q[min(qi, len(q)-1)]):
        break
    else:
        if pi >= len(p) and qi >= len(q):
            break
        else:
            if pi < len(p) and qi < len(q):
                if p[pi] < q[qi]:
                    p[pi] = r[ri]
                    pi += 1
                else:
                    q[qi] = r[ri]
                    qi += 1
            elif pi < len(p) and qi >= len(q):
                p[pi] = r[ri]
                pi += 1
            else:
                q[qi] = r[ri]
                qi += 1
            ri += 1
print(sum(p[-x:]) + sum(q[-y:]))
import numpy as np
N =int(input())
A =[]
B =[]
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
index = np.argsort(B)
time = 0
f = 0
for i in index:
    time += A[index]
    if time>B[index]:
        f = 1
        break
if f == 1:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

import numpy as np
N =int(input())
A =[]
B =[]
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
index = np.argsort(B)
time = 0
f = 0
for i in index:
    time += A[i]
    if time>B[i]:
        f = 1
        break
if f == 1:
    print('No')
else:
    print('Yes')
import numpy as np

s = input()
mod = 10**9+7

dp = np.zeros((len(s)+1, 13))
dp[0][0] = 1

for i in range(len(s)):
  c = -1 if s[i] == '?' else int(s[i])
  for j in range(10):
    if (c != -1 and c != j):
      continue
    for k in range(13):
      dp[i+1][(k * 10 + j) % 13] += dp[i][k]
      dp[i+1][(k * 10 + j) % 13] %= mod
		
  for j in range(13):
    dp[i+1][j] %= mod    
  
print(int(dp[len(s)][5]))



### FIXED CODE ###

s = input()
mod = 10**9+7

dp = [[0 for j in range(13)] for i in range(len(s)+1)]
dp[0][0] = 1
for i in range(len(s)):
  c = -1 if s[i] == '?' else int(s[i])
  for j in range(10):
    if (c != -1 and c != j):
      continue
    for k in range(13):
      dp[i+1][(k * 10 + j) % 13] += dp[i][k]
      dp[i+1][(k * 10 + j) % 13] %= mod
		
  for j in range(13):
    dp[i+1][j] %= mod    
  
print(int(dp[len(s)][5]))
def resolve():
    N, M = [int(i) for i in input().split()]
    path = [[] for _ in range(N)]
    for _ in range(M):
        A, B = [int(i) for i in input().split()]
        path[A - 1].append(B - 1)
        path[B - 1].append(A - 1)
    visited = [-1] * N
    que = [0]
    visited[0] = 0

    while que:
        v = que.pop(0)
        print(v, path[v], file=sys.stderr)
        for nv in path[v]:
            if visited[nv] != -1:
                continue
            print(nv, visited[v] + 1, file=sys.stderr)
            visited[nv] = v + 1
            que.append(nv)

    if -1 in visited:
        print("No")
    else:
        print("Yes")
        for i in range(N - 1):
            print(visited[i + 1])


resolve()


### FIXED CODE ###

def resolve():
    N, M = [int(i) for i in input().split()]
    path = [[] for _ in range(N)]
    for _ in range(M):
        A, B = [int(i) for i in input().split()]
        path[A - 1].append(B - 1)
        path[B - 1].append(A - 1)
    visited = [-1] * N
    que = [0]
    visited[0] = 0

    while que:
        v = que.pop(0)
        for nv in path[v]:
            if visited[nv] != -1:
                continue
            visited[nv] = v + 1
            que.append(nv)

    if -1 in visited:
        print("No")
    else:
        print("Yes")
        for i in range(N - 1):
            print(visited[i + 1])


resolve()
from math import pi

R = input()

print(R*R*pi)

### FIXED CODE ###

from math import pi

r = int(input())

print(2*r*pi)
n=int(input())
import sympy
ans=0
for i in range(1,n):
    ans+=len(sympy.divisors(i))
print(ans)

### FIXED CODE ###

n=int(input())

ans=0
for i in range(1,n):
    ans+=(n-1)//i
print(ans)
import math

n = int(input())

sqrt_n = int(math.sqrt(n))

for i in reversed(range(sqrt_n)):
  if(n%i == 0):
    print(i + n%i -2)

### FIXED CODE ###

import math
 
n = int(input())
 
sqrt_n = int(math.sqrt(n))
 
for i in reversed(range(sqrt_n+1)):
  if(n%i == 0):
    print(i+int(n/i)-2)
    break
x = input()
y = x[-1]
if y == 3:
  print("bon")
elif y == 0,1,6,8:
  print("pon")
else:
  print("hon")

### FIXED CODE ###

x = int(input())
y = x%10
if y == 3:
  print("bon")
elif y == 0:
  print("pon")
elif y == 1:
  print("pon")
elif y == 6:
  print("pon")
elif y == 8:
  print("pon")
else:
  print("hon")
from fractions import *
import sys
N, M = map(int, input().split())

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

a = sorted(a)
bc = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

bc = sorted(bc)    

subar = a
for i in bc:
    sc = [i[1]] * i[0]
    suba = []
    ra = subar[i[0]:]
    if i[0] == len(a):
        suba = a
    suba = subar[:i[0]]
    if i[1] - max(suba) < 0:
        continue
    subar = sc + ra
    subar.sort()

print(sum(subar))





### FIXED CODE ###

from fractions import *
a, b = map(int, input().split())

if a<= 5:
    print(0)
elif 6 <= a and a <= 12:
    print(int(b/2))
else:
    print(b)
X, K, D = map(int, input().split())
X = abs(X)
r = X % D
t = X // D
if t >= K:
    ans = abs(X - K * D)
elif (K - t) % 2 == 0:
    ans = r
else:
    ans = D - r
print(ans)

### FIXED CODE ###

S = input()
cnt = 0
ans = 0
for s in S:
    if s == 'R':
        cnt += 1
    else:
        cnt = 0
    ans = max(ans, cnt)
print(ans)
print(input().count(1))


### FIXED CODE ###

print(input().count('1'))
n,k=map(int,input().split())
h=list(map(int,input().split()))

h.sort(reverse=True)

for i in range(k):
  h[i]=0

sum_=0
for hh in h:
  sum_+=hh
print(sum_)

### FIXED CODE ###

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

h.sort(reverse=True)

if k>n:
  k=n

for i in range(k):
  h[i]=0

sum_=0
for hh in h:
  sum_+=hh
print(sum_)
count = 0

length = int(input())
length_list = map(int, input().split())

for i in range(length - 2):
    for j in range(i + 1, length - 1):
        if length_list[i] != length_list[j]:
            for k in range(j + 1, length):
                if length_list[j] != length_list[k] and length_list[k] != length_list[i]:
                    half_length_sum = (length_list[i] + length_list[j] + length_list[k]) / 2
                    if half_length_sum > max(length_list[i], length_list[j], length_list[k]):
                        count += 1
print(count)

### FIXED CODE ###

count = 0

length = int(input())
length_list = list(map(int, input().split()))

for i in range(length - 2):
    for j in range(i + 1, length - 1):
        if length_list[i] != length_list[j]:
            for k in range(j + 1, length):
                if length_list[j] != length_list[k] and length_list[k] != length_list[i]:
                    half_length_sum = (length_list[i] + length_list[j] + length_list[k]) / 2
                    if half_length_sum > max(length_list[i], length_list[j], length_list[k]):
                        count += 1
print(count)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
A = [int(x) for x in input().split()]

ntom = dict(zip(
        range(1,N+1),
        [2,5,5,4,5,6,3,7,6]
       ))

mtoa = {}
for a in A:
    m = ntom[a]
    mtoa[m] = max(mtoa.get(m, 0), a)

ms = mtoa.keys()
dp = [float('-inf')] * (N+1)
dp[0] = 0
for i in range(min(ms), N+1):
    dp[i] = max(dp[i-x] for x in ms if i >= x) + 1

mms = sorted([(v, m) for m, v in mtoa.items()], reverse=True)
ans = []
left = N
while left:
    for v,m in mms:
        if left >= m and dp[left] == dp[left - m] + 1:
            left -= m
            ans.append(v)
            break
        
print(*ans, sep='')

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
A = [int(x) for x in input().split()]

ntom = [0,2,5,5,4,5,6,3,7,6]

mtoa = {}
for a in sorted(A):
    mtoa[ntom[a]] = a

ms = sorted(mtoa.keys(), key=lambda x: mtoa[x], reverse=True)
dp = [0] + [float('-inf')] * N
for i in range(min(ms), N+1):
    dp[i] = max(dp[i-x] for x in ms if i >= x) + 1

ans = []
left = N
while left:
    for m in ms:
        if left >= m and dp[left] == dp[left - m] + 1:
            left -= m
            ans.append(mtoa[m])
            break
        
print(*ans, sep='')
a,b=map(int,input().split())

if (500*a => b):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b=map(int,input().split())
 
if (500*a >= b):
  print("Yes")
else:
  print("No")
def main():
    k = input()
    n = [
        1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
    ]
    print(n[k])
main()


### FIXED CODE ###

def main():
    k = input()
    n = [
        1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
    ]
    print(n[int(k) - 1])
main()
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

N, M, K = map(int, input().split())
uf = UnionFind(N)

friend =[[] for _ in range(N)]
block = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    uf.union(a, b)
    friend[a].append(b)
    friend[b].append(a)

for i in range(k):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if uf.same(c, d):
        block[c].append(d)
        block[d].append(c)
ans = [0] * N
for i in range(N):
    ans[i] = uf.size(i) - len(friend[i]) - len(block[i]) - 1
print(*ans)


### FIXED CODE ###

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

N, M, K = map(int, input().split())
uf = UnionFind(N)

friend =[[] for _ in range(N)]
block = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    uf.union(a, b)
    friend[a].append(b)
    friend[b].append(a)

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if uf.same(c, d):
        block[c].append(d)
        block[d].append(c)
ans = [0] * N
for i in range(N):
    ans[i] = uf.size(i) - len(friend[i]) - len(block[i]) - 1
print(*ans)
N= map(int,input().split())

if N=

### FIXED CODE ###

N= int(input())

print(N//3)
# coding: utf-8
import time
import re
import math

def main():
    n=int(input())
    k=int(input())
    X=map(int,input().split())
    total=0
    for a in X:
        total+=min([a,math.abs(k-a)])*2
    print(int(total))
main()

### FIXED CODE ###

# coding: utf-8
import time
import re
import math

def main():
    n=int(input())
    k=int(input())
    X=map(int,input().split())
    total=0
    for a in X:
        total+=min([a,abs(k-a)])*2
    print(int(total))
main()
#coding:utf-8
N = int(input())
D = list(map(int,input().split()))
D = sorted(D)
idx = len(D) // 2
print(D[idx] - D[odx-1])

### FIXED CODE ###

#coding:utf-8
N = int(input())
D = list(map(int,input().split()))
D = sorted(D)
#print (D)
a = D[int(len(D)/2)-1:int(len(D)/2)+1]
print (a[1]-a[0])
N,A,B=map(int,input().split())

line =''

for i in range(10**100):
    line += 'b'*A
    line += 'r'*B
    if len(line)>=N:
        print(line[:N].count('b'))
        break

### FIXED CODE ###

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

ans =N//(A+B)*A
remain = N%(A+B)
ans += min(remain,A)
print(ans)
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 銀貨を何枚持っているかの状態数、N*2501の都市, dijkstra
N, M, S = lr()
limit = 2500
graph = [[] for _ in range((N+1) * (limit+1))]  # 1-indexed
for _ in range(M):
    u, v, a, b = lr()
    for x in range(a, limit+1):
        graph[u*(limit+1) + x].append(((v*(limit+1)+x-a), b))
        graph[v*(limit+1) + x].append(((u*(limit+1)+x-a), b))

for i in range(N):
    i += 1
    c, d = lr()
    for x in range(limit-c+1):
        graph[i*(limit+1) + x].append((i*(limit+1) + x + c, d))

def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * ((N+1) * (limit+1))
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, time in graph[prev]:
            d1 = d + time
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

dist = dijkstra(1*(limit+1)+S)
for i in range(2, N+1):
    answer = min(dist[i*(limit+1):(i+1)*(limit+1)])
    print(answer)



### FIXED CODE ###

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 同じ地点で銀貨の枚数によって別の状態として扱う（最大max(A)*(N-1))
N, M, S = lr()
UVAB = [lr() for _ in range(M)]
CD = [lr() for _ in range(N)]  # 0-indexed
Amax = 0
for i in range(M):
    a = UVAB[i][2]
    if a > Amax:
        Amax = a

limit = Amax*(N-1)
S = min(S, limit)
graph = [[] for _ in range(N+1)] # 1-indexed
for u, v, a, b in UVAB:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start):
    # 時間、銀貨の枚数、現在地をqueへ
    INF = 10 ** 15
    dist = [[INF for _ in range(limit+1)] for _ in range(N+1)]
    dist[1][S] = 0
    que = [(0, S, 1)]
    while que:
        time, silver, prev = heappop(que)
        if dist[prev][silver] < time:
            continue
        for next, a, b in graph[prev]:
            t = time + b
            si = silver - a
            if si < 0:
                continue
            if dist[next][si] > t:
                dist[next][si] = t
                heappush(que, (t, si, next))
        c, d = CD[prev-1]
        si = min(limit, silver+c)
        while dist[prev][si] > time + d:
            dist[prev][si] = time + d
            heappush(que, (time+d, si, prev))
            si += c; si = min(limit, si)
            time += d
            
    return dist

dist = dijkstra(1)
for i in range(2, N+1):
    d = dist[i]
    answer = min(d)
    print(answer)

# 52