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

import heapq

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

for i in range(M):
    B,C = map(int,input().split())
    D = [C]* B
    A = A + D
    
a = list(map(lambda x: x*(-1), A))
heapq.heapify(a)

ans = 0
for i in range(N):
    ans += heapq.heappop(a)*(-1)
    
print(ans)

### FIXED CODE ###

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

L = []
for i in range(M):
    bc = tuple(map(int,input().split()))
    L.append(bc)

L = sorted(L,key=lambda x:-x[1])
n = 0
for b,c in L:
    n += b
    A += [c] * b
    if n >= N:
        break
        
A.sort()
print(sum(A[-N:]))
### BUGGY CODE ###

def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()

    from heapq import heappush, heappop 

    running = []
    events = []
    delete = set()

    n, q = map(int, input().split())
    for _ in range(n):
        s, t, x = map(int, input().split())
        time = max(s - x, 0)
        if t - x < 0:
            continue
        events.append((s - x, x, 1)) # 追加イベント
        events.append((t - x, x, 0)) # 削除イベント
    events.sort()
    ans = []
    idx = -1
    for _ in range(q):
        d = int(input())
        if d >= events[-1][0]:
            print(-1)
            continue
        while events[idx + 1][0] <= d:
            idx += 1
            if events[idx][2] == 1:
                heappush(running, events[idx][1])
                delete.discard(events[idx][1])
            else:
                delete.add(events[idx][1])
        flag = 1
        while running:
            x = heappop(running)
            if x not in delete:
                heappush(running, x)
                print(x)
                flag = 0
                break
        if flag:
            print(-1)
if __name__ == '__main__':
    main()





### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

from heapq import heappush, heappop 

running = []
events = []
delete = set()

n, q = map(int, input().split())
for _ in range(n):
    s, t, x = map(int, input().split())
    time = max(s - x, 0)
    if t - x < 0:
        continue
    events.append((s - x, x, 1)) # 追加イベント
    events.append((t - x, x, 0)) # 削除イベント
events.sort()
ans = []
idx = -1
for _ in range(q):
    d = int(input())
    if d >= events[-1][0]:
        print(-1)
        #ans.append(-1)
        continue
    while events[idx + 1][0] <= d:
        idx += 1
        if events[idx][2] == 1:
            heappush(running, events[idx][1])
            delete.discard(events[idx][1])
        else:
            delete.add(events[idx][1])
    flag = 1
    while running:
        x = heappop(running)
        if x not in delete:
            heappush(running, x)
            print(x)
            #ans.append(x)
            flag = 0
            break
    if flag:
        print(-1)
### BUGGY CODE ###

from collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    AB = sorted(AB, key=lambda it: it[1], reverse=True)

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []
    for i in range(1, M + 1):
        q += ARR[i]
        q = sorted(q)
        # print(q)
        if len(q) != 0:
            mm = q.pop()
            res += mm
    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    # AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []
    for i in range(1, M + 1):
        current = ARR[i]
        for a in current:
            heapq.heappush(q, -a)
        if len(q) != 0:
            res -= heapq.heappop(q)
    print(res)


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

INF = 1145141919810893

H,N = map(int,input().split())
A=[]
B=[]
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

#dp[i]=体力がちょうどiのモンスターを倒すのに必要な魔力の最小値
#もしそのような魔力が存在しない場合、INF
#INFは10^9くらいあれば足りると思う(適当)
dp = [INF]*20000
dp[0]=0
#体力が0のモンスターを倒すのに必要な魔力は0
#iは小さい順に決定することができる
#なぜなら、i<jのとき決定したdp[j]の値はdp[i]に影響しないから
for i in range(H):
    #dp[H]から配る遷移は、必ずdp[H]より大きい値を配ることになるので、不要
    #よってH-1までやればOK
    #dp[i]の値はこの時点で確定する
    if dp[i]==INF:
        continue
    for j in range(N):
        #いわゆる配るDP
        dp[i+A[j]]=min(dp[i+A[j]],dp[i]+B[j])

#これで答えはdp[H]であるかというと、そうとは限らない
#なぜなら、dp[H+1]に行くコストがdp[H]に行くコストより安いかもしれないから
#今回は「与えるダメージがH以上」で条件を達成することができる
#なので、H以上のdpについて精査して、最もコストが低いものが答えである
Ans=INF
for d in dp[H:]:
    Ans=min(Ans,d)
print(Ans)





### FIXED CODE ###

INF = 1145141919810893

H,N = map(int,input().split())
A=[]
B=[]
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

#dp[i]=体力がちょうどiのモンスターを倒すのに必要な魔力の最小値
#もしそのような魔力が存在しない場合、INF
#INFは10^9くらいあれば足りると思う(適当)
dp = [INF]*20000
dp[0]=0
#体力が0のモンスターを倒すのに必要な魔力は0
#iは小さい順に決定することができる
#なぜなら、i<jのとき決定したdp[j]の値はdp[i]に影響しないから
for i in range(H):
    #dp[H]から配る遷移は、必ずdp[H]より大きい値を配ることになるので、不要
    #よってH-1までやればOK
    #dp[i]の値はこの時点で確定する
    if dp[i]==INF:
        continue
    for j in range(N):
        #いわゆる配るDP
        dp[i+A[j]]=min(dp[i+A[j]],dp[i]+B[j])

#これで答えはdp[H]であるかというと、そうとは限らない
#なぜなら、dp[H+1]に行くコストがdp[H]に行くコストより安いかもしれないから
#今回は「与えるダメージがH以上」で条件を達成することができる
#なので、H以上のdpについて精査して、最もコストが低いものが答えである
Ans=INF
for d in dp[H:]:
    Ans=min(Ans,d)
print(Ans)
### BUGGY CODE ###

def solve():
    n, k = map(int, input().split())
    h = sorted(list(int(input()) for _ in range(n)))
    min_diff = 10 ** 9
    for i in range(n - k + 1):
        part = h[i:i + k]
        diff = part[-1] - part[0]
        if diff < min_diff:
            min_diff = diff
    return min_diff


if __name__ == "__main__":
    print(solve())


### FIXED CODE ###

def solve():
    n, k = map(int, input().split())
    h = sorted(list(int(input()) for _ in range(n)))
    return min(h[i + k - 1] - h[i] for i in range(n - k + 1))


if __name__ == "__main__":
    print(solve())
### BUGGY CODE ###

from itertools import groupby

N = int(input())
S = input()

t = S[1:]
c = 0
for i in range(1, N):
    # print(S, t, i)
    for k, g in groupby([a == b for a, b in zip(S, t)]):
        if k == False:
            continue
        x = len(tuple(g))
        c = max(c, min(i, x))
    t = t[1:]
# print(S, t)
print(c)


### FIXED CODE ###

N = int(input())
S = [ord(s) for s in input()]
# N = 5000
# S = "abcdefg" + "k"*4993

c = 0
for i in range(1, N):
    d = 0
    for s_j, t_j in zip(S, S[i:]):
        if s_j == t_j:
            d += 1
        else:
            c = max(c, min(d, i))
            d = 0
    c = max(c, min(d, i))

# print(S, t)
print(c)
### BUGGY 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()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
STX.sort(key=lambda x: x[2], reverse=True)
event = []
for s, t, x in STX:
    s = max(-1, s-x)
    t = max(0, t-x)
    event.append((s, 0, x))
    event.append((t, -1, x))

answer = [None] * Q
for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort(key=lambda x: [x[0], x[1]])
cur = []
used = set()
for a, b, c in event:
    if b == 0:
        if c in used:
            used.remove(c)
        heappush(cur, c)
    elif b == -1:
        used.add(c)
    elif b == 1:
        while cur and cur[0] in used:
            heappop(cur)
        if cur:
            answer[c] = cur[0]
        else:
            answer[c] = -1

print('\n'.join(map(str, answer)))
# 19

### FIXED CODE ###

# coding: utf-8
import sys

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

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
event = []
for s, t, x in STX:
    event.append((s-x, 0, x))
    event.append((t-x, -1, x))

for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort()
answer = [-1] * Q
cur = set()
flag = False
INF = 10 ** 10
min_x = INF
for a, b, c in event:
    if b == 0:
        cur.add(c)
        if c < min_x:
            min_x = c
            flag = True
    elif b == -1:
        cur.remove(c)
        if min_x == c:
            flag = False
    elif b == 1:
        if cur:
            if not flag:
                min_x = min(cur)
                flag = True
            answer[c] = min_x

print('\n'.join(map(str, answer)))
# 19
### BUGGY CODE ###

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (2 ** n)
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
for s in range(2 ** n):
    otoko = bin(s).count("1")
    i = otoko
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[2 ** n - 1])


### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (pow(2, n))
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
bitcnt = [0] * (pow(2, n) + 1)
for s in range(pow(2, n)):
    # otoko = bin(s).count("1")
    bitcnt[s] = bitcnt[s // 2] + s % 2
    i = bitcnt[s]
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[pow(2, n) - 1])
### BUGGY CODE ###

from heapq import heappush, heappop
import time
stime=time.time()
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    if time.time()-stime>1.8:
        break
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    if v==n+1:
        break
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])


### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])
### BUGGY CODE ###

A, B, K = map(int, input().split())
[print(i) for i in range(A, B+1) if i-A <= K-1 or B-i <= K-1]

### FIXED CODE ###

A, B, K = map(int, input().split())
for a in sorted(list(set([i for i in range(A, min(A + K, B+1))]) | set([i for i in range(max(A, B-K+1), B+1)]))):
    print(a)
### BUGGY CODE ###

H, W = map(int, input().split())

while True:
    if (H + W == 0) : break
    
    for i in range(0, H-1):
        print('#' * W)



### FIXED CODE ###

while True:
    H, W = map(int, input().split())

    if (H + W == 0) : break
    
    for i in range(H):
        print('#' * W)

    print()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(1, N+1):
    print(A.index(i)+1, end=' ')


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0] * N
for (i, x) in enumerate(A):
    B[x-1] = i+1
for b in B:
    print(b, end=' ')
### BUGGY CODE ###

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

s = input()
t = input()
n = len(s)
m = len(t)
dp = [['']*(m+5) for i in range(n+5)]
for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
        else:
            dp[i+1][j+1] = dp[i][j+1] if len(dp[i][j+1]) >= len(dp[i+1][j]) else dp[i+1][j]
print(dp[n][m])

### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

S = input()
T = input()
ls = len(S)
lt = len(T)
dp = [[0 for _ in range(lt+5)] for i in range(ls+5)]
#最大値を求める
for i in range(ls):
    for j in range(lt):
        if S[i] == T[j]:
            dp[i+1][j+1] = max(dp[i][j]+1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

#復元部分
i = ls
j = lt
ans = ''
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        ans = S[i-1] + ans
        i -= 1
        j -= 1
print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1
	a = 1
	for i in range(1,length):
		a = 10 * a % 13
		if s[-i-1] != '?':
			num = int(s[-i-1])
			for j in range(13):
				dp[i][(a*num+j)%13] = dp[i-1][j]
				dp[i][(a*num+j)%13] %= MOD
		else:
			num = (10**i) % 13
			#a = 0
			for j in range(10):
				for k in range(13):
					dp[i][(a*j+k)%13] += dp[i-1][k]
					dp[i][k] %= MOD
				#a += num

	print(dp[-1][5] % MOD)

if __name__ == '__main__':
	main()

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

def main():
    from itertools import permutations
    import math
    import numpy as np
    tot = 0

    N = int(input())
    locs = np.array([
        [int(x) for x in input().split()]
        for _ in range(N)
    ])

    for order in permutations(range(N)):
        d = 0
        for i in range(N-1):
            i0 = order[i]
            i1 = order[i+1]
            d += np.linalg.norm(locs[i0]-locs[i1])
        tot += d
    print(tot/math.factorial(N))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    from itertools import permutations
    import math
    import numpy as np
    tot = 0

    N = int(input())
    locs = np.array([
        [int(x) for x in input().split()]
        for _ in range(N)
    ], dtype=float)

    for order in permutations(range(N)):
        order = list(order)
        loc0 = locs[order[:-1]]
        loc1 = locs[order[1:]]
        delta = loc1 - loc0
        tot += np.sum(np.linalg.norm(delta, axis=1))
    print(tot/math.factorial(N))


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

n=int(input())
S=[]
for _ in range(n):
    s=str(input())
    if s in S:
        continue
    else:
        S.append(s)
print(len(S))


### FIXED CODE ###

n=int(input())
S=set()
for _ in range(n):
    s=str(input())
    if s in S:
        continue
    else:
        S.add(s)
print(len(S))
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
SUM = sum(a)
MIN = 10**10
for i in range(N-1):
    suma = sum(a[:i+1])
    sumb = SUM-suma
    kari = abs(suma-sumb)
    MIN = min(MIN,kari)
print(MIN)

### FIXED CODE ###

def solve(N,a):
    suma = 0
    SUM = sum(a)
    MIN = 10**15
    for i in a[:(N-1)]:
        suma+=i
        MIN = min(MIN,abs(2*suma-SUM))
    return abs(MIN)

if __name__ == "__main__":
    N = int(input())
    a = list(map(int,input().split()))
    print(solve(N,a))
### BUGGY CODE ###

import sys

input = sys.stdin.readline

x, y, z, k = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))
a_list.sort(reverse=True)
b_list.sort(reverse=True)
c_list.sort(reverse=True)
tmp_list = [a+b for a in a_list for b in b_list]
tmp_list.sort(reverse=True)
honest_list = [tmp+c for tmp in tmp_list for c in c_list]
honest_list.sort(reverse=True)
for h in honest_list[:k]:
    print(h)


### FIXED CODE ###

import sys

input = sys.stdin.readline

x, y, z, k = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))
a_list.sort(reverse=True)
b_list.sort(reverse=True)
c_list.sort(reverse=True)
tmp_list = [a+b for a in a_list for b in b_list]
tmp_list.sort(reverse=True)
honest_list = [tmp+c for tmp in tmp_list[:k] for c in c_list]
honest_list.sort(reverse=True)
for h in honest_list[:k]:
    print(h)
### BUGGY CODE ###

s = input()
K = int(input())
pool = set()

for i in range(len(s)):
  for j in range(i+ 1, len(s)+ 1):
    news = s[i:j]
    pool.add(news)
    
plis = list(pool)
plis.sort()

print(plis[K- 1])

### FIXED CODE ###

s = input()
K = int(input())
pool = set()
n = 0
slist = list(s)

for i in range(26):
  c = s.count(chr(97+ i))
  for j in range(c):
    index = slist.index(chr(97+ i))
    slist[index] = ""
    for k in range(len(s)- index):
      pool.add(s[index:index+ k+ 1])
      if(k>= K):
        break
  if(len(pool)>= K):
    newlist = list(pool)
    newlist.sort()
    print(newlist[K- 1])
    break
### BUGGY CODE ###

n, q = map(int, input().split())
s = list(str(input()))


for i in range(q):
    l, r = map(int,input().split())
    subs = s[l-1:r]
    subs = ''.join(subs)
    print(subs.count('AC'))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()


t = [0] * (n+1)
for i in range(n):
    if s[i:i+2] == 'AC':
        t[i+1] = t[i] + 1
    else:
        t[i+1] = t[i]

        
for i in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

import numpy as np
import functools
import math
import scipy
import fractions
import itertools

def solve():
    x = input()
    le = len(x)
    while True:
        bit = 0
        for i in range(le-1):
            if x[i:i+2] == "ST":
                x = x[0:i]+x[i+2:le]
                bit = 1
                le -= 2
                break
        if bit == 0:
            print(len(x))
            break

    return 0
 
if __name__ == "__main__":
    solve()


### FIXED CODE ###

import numpy as np
import functools
import math
import scipy
import fractions
import itertools
 
def solve():
    x = input()
    a, b = 0, 0
    for i in x:
        if i == "S":
            a += 1
        else:
            if a == 0:
                b += 1
            else:
                a -= 1
    print(a + b)
    return 0

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

def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append([v-1,a,b])
    g[v-1].append([u-1,a,b])
  import heapq
  from collections import defaultdict
  import math
  dp=[[math.inf]*(100*51)for _ in range(n)]
  kakutei=[[0]*(100*51)for _ in range(n)]
  dp[0][min(s,100*51-1)]=0
  todo=[[0,0,min(s,100*51-1)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flg=[0]*n
  while all(flg)!=1:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    flg[v]=1
    c,d=cd[v]
    # 両替
    dp[v][min(100*51-1,i+c)]=min(dp[v][min(100*51-1,i+c)],dp[v][i]+d)
    heapq.heappush(todo,[dp[v][min(100*51-1,i+c)],v,min(100*51-1,i+c)])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  for i in range(1,n):
    print(min(dp[i]))
  #for i in range(n):
  #  print(dp[i][:10])
if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()
### BUGGY CODE ###

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


mod = 1000000007;
n = int(input())
a = list(map(int, input().split()))

LCM = 1
for i in a:
    LCM = LCM // gcd(LCM,i) * i

ans = 0
for i in a:
    ans += (LCM // i)
    ans %= mod

print(ans)


### FIXED CODE ###

import fractions 
mod = 1000000007;
n = int(input())
a = list(map(int, input().split()))

LCM = 1
for i in a:
    LCM = LCM // fractions.gcd(LCM,i) * i

ans = 0
for i in a:
    ans += (LCM // i)

ans %= mod
print(ans)