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

import sys
sys.setrecursionlimit(4100000)
N = int(input())
tree = [[] for _ in range(N+1) ]
already_make = [-1]*(N+1)
for i in range(1,N):
    a,b = map(int,input().split(' '))
    tree[a].append([b,i])

last_color = 0
bfs_use_coler = [[ -1 for _ in range(N+1) ] for _ in range(N+1) ] 

def solve(n,last_color):
    '''
    use_colers =[]
    for val in bfs_use_coler[0:n-2]:
        use_colers = use_colers + val
    '''
    for val in tree[n]:
        if already_make[val[1]] != -1:
            continue
        use_coloer = -1
        length = last_color+1
        for i in range(1,length):
            if bfs_use_coler[val[0]][i] == 1 or bfs_use_coler[n][i] == 1:
                continue
            else:
                use_coloer = i
                break
        if use_coloer == -1:
            last_color +=1
            use_coloer = last_color
        bfs_use_coler[val[0]][use_coloer] = 1
        bfs_use_coler[n][use_coloer] = 1
        already_make[val[1]] = use_coloer
    return last_color

for i in range(1,N+1):
    last_color = solve(i,last_color)
print(last_color)
for val in already_make[1:N]:
    print(val)


### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
N = int(input())
tree = [[] for _ in range(N+1) ]
already_make = [-1]*(N+1)
for i in range(1,N):
    a,b = map(int,input().split(' '))
    tree[a].append([b,i])

last_color = 0
#bfs_use_coler = [[ -1 for _ in range(N+1) ] for _ in range(N+1) ] 

def solve_bfs(previous_colors,n_list,last_color):
    '''
    use_colers =[]
    for val in bfs_use_coler[0:n-2]:
        use_colers = use_colers + val
    '''
    next_colors = []
    next_n_list =[]
    for idx1,n in enumerate(n_list):
        use_color_num = 1
        for idx2,val in enumerate(tree[n]):
            if use_color_num == previous_colors[idx1]:
                use_color_num += 1
            already_make[val[1]] = use_color_num
            next_colors.append(use_color_num)
            next_n_list.append(val[0])
            last_color = max(use_color_num,last_color)
            use_color_num += 1
    if len(next_colors) > 0:
        return solve_bfs(next_colors,next_n_list,last_color)
    else:
        return last_color

last_color = solve_bfs([0],[1],last_color)
print(last_color)
for val in already_make[1:N]:
    print(val)
### BUGGY CODE ###

H, W = map(int, input().split())
field = [input() for _ in range(H)]

# Left
Left = [[0] * W for _ in range(H)]
for h in range(H):
    cnt = 0
    for w in range(W):
        if field[h][w] == '#':
            cnt = 0
        else:
            cnt += 1
        Left[h][w] = cnt

# Right
Right = [[0] * W for _ in range(H)]
for h in range(H):
    cnt = 0
    for w in range(W-1, -1, -1):
        if field[h][w] == '#':
            cnt = 0
        else:
            cnt += 1
        Right[h][w] = cnt

# Up
Up = [[0] * W for _ in range(H)]
for w in range(W):
    cnt = 0
    for h in range(H):
        if field[h][w] == '#':
            cnt = 0
        else:
            cnt += 1
        Up[h][w] = cnt

# Down
Down = [[0] * W for _ in range(H)]
for w in range(W):
    cnt = 0
    for h in range(H-1, -1, -1):
        if field[h][w] == '#':
            cnt = 0
        else:
            cnt += 1
        Down[h][w] = cnt

# 集計
ans = -1
for h in range(H):
    for w in range(W):
        ans = max(ans, Left[h][w] + Right[h][w] + Up[h][w] + Down[h][w] - 3)
print(ans)



### FIXED CODE ###

H, W = map(int, input().split())
field = [input() for _ in range(H)]

# Left
Left = [[0] * W for _ in range(H)]
for h in range(H):
    cnt = 0
    for w in range(W):
        if field[h][w] == '#':
            cnt = 0
        else:
            cnt += 1
        Left[h][w] = cnt

# Right
Right = [[0] * W for _ in range(H)]
for h in range(H):
    cnt = 0
    for w in range(W-1, -1, -1):
        if field[h][w] == '#':
            cnt = 0
        else:
            cnt += 1
        Right[h][w] = cnt

# Up
Up = [[0] * W for _ in range(H)]
for w in range(W):
    cnt = 0
    for h in range(H):
        if field[h][w] == '#':
            cnt = 0
        else:
            cnt += 1
        Up[h][w] = cnt

# Down
Down = [[0] * W for _ in range(H)]
for w in range(W):
    cnt = 0
    for h in range(H-1, -1, -1):
        if field[h][w] == '#':
            cnt = 0
        else:
            cnt += 1
        Down[h][w] = cnt

# 集計
ans = -1
for h in range(H):
    for w in range(W):
        ans = max(ans, Left[h][w] + Right[h][w] + Up[h][w] + Down[h][w] - 3)
print(ans)
### BUGGY CODE ###

A = list(map(int , input().split()))
B = list(map(int , input().split()))
if A[0] < A[1]:
    print(0)
else:
    B.sort(reverse=True)
    for i in range(A[1]):
        B.remove(max(B))
    print(sum(B))

### FIXED CODE ###

A = list(map(int , input().split()))
B = list(map(int , input().split()))
if A[0] < A[1]:
    print(0)
else:
    B.sort(reverse=True)
    del B[0:A[1]]
    print(sum(B))
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def calc():
  n=int(input())
  arr=list(map(int,input().split()))
  l=int(input())
  pos=0
  dbl=[[0]*(n+1)]
  for i in range(n):
    for j in range(pos,n):
      if arr[j]-arr[i]>l:
        dbl[0][i+1]=j
        pos=j
        break
    else:
      dbl[0][i+1]=n
  for _ in range(n.bit_length()-1):
    tmp=[0]*(n+1)
    for i in range(n+1):
      tmp[i]=dbl[-1][dbl[-1][i]]
    dbl.append(tmp)
  q=int(input())
  for _ in range(q):
    a,b=map(int,input().split())
    if a>b:
      a,b=b,a
    l=0
    r=b-a+1
    while r-l!=1:
      mid=(l+r)//2
      tmp=a
      for i in range(mid.bit_length()):
        if mid&(1<<i):
          tmp=dbl[i][tmp]
      if tmp>=b:
        r=mid
      else:
        l=mid
    print(r)
calc()

### FIXED CODE ###

import bisect
import sys
input=sys.stdin.readline

def calc():
  n=int(input())
  arr=list(map(int,input().split()))
  l=int(input())
  pos=0
  dbl=[[0]*(n+1)]
  for i in range(n):
      dbl[0][i+1]=bisect.bisect_right(arr,arr[i]+l)
  for _ in range(n.bit_length()-1):
    tmp=[0]*(n+1)
    for i in range(n+1):
      tmp[i]=dbl[-1][dbl[-1][i]]
    dbl.append(tmp)
  q=int(input())
  for _ in range(q):
    a,b=map(int,input().split())
    if a>b:
      a,b=b,a
    l=0
    r=b-a+1
    while r-l!=1:
      mid=(l+r)//2
      tmp=a
      for i in range(mid.bit_length()):
        if mid&(1<<i):
          tmp=dbl[i][tmp]
      if tmp>=b:
        r=mid
      else:
        l=mid
    print(r)
calc()
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
cities = [[] for _ in range(n)]
ans = [None] * m
idxMap = {}

for i in range(m):
    p, y = map(int, input().split())
    # idx = bisect.bisect_left(cities[p-1], y)
    # cities[p-1].insert(idx, y)
    bisect.insort_left(cities[p-1], y)
    idxMap[y] = i

    # ans.append(str(p).zfill(6) + str(idx+1).zfill(6))
    # py.append(list(map(int, input().split())))

for i in range(n):
    for j in range(len(cities[i])):
        year = cities[i][j]
        idx = idxMap[year]
        ans[idx] = str(i+1).zfill(6) + str(j+1).zfill(6)

# print(cities)
for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

import bisect

n, m = map(int, input().split())
cities = [[] for _ in range(n)]
ans = [None] * m
idxMap = {}

for i in range(m):
    p, y = map(int, input().split())
    # bisect.insort_left(cities[p-1], y)
    cities[p-1].append(y)
    idxMap[y] = i

    # ans.append(str(p).zfill(6) + str(idx+1).zfill(6))
    # py.append(list(map(int, input().split())))

for i in range(n):
    cities[i].sort()

# print('cities:', cities)

for i in range(n):
    for j in range(len(cities[i])):
        year = cities[i][j]
        idx = idxMap[year]
        ans[idx] = str(i+1).zfill(6) + str(j+1).zfill(6)

# print(cities)
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
result = 0
A = [0]

for i in range(len(P)-K+1):
    if sum(P[i:i+K]) > result:
        result = sum(P[i:i+K])
        A = P[i:i+K]

answer = 0

for a in A:
    answer += a/2+0.5

print(answer)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
result = 0
B = [a / 2 + 0.5 for a in P]

result = sum(B[0:K])
t = sum(B[0:K])
for i in range(N-K):
    t -= B[i]
    t += B[i+K]
    if t > result:
        result = t

print(result)
### BUGGY CODE ###

from collections import deque
s=input()
k=int(input())
right=0
left=0
r=deque([])
while right<len(s):
  r.append(s[right:left+1])
  left+=1
  if left==len(s):
    right+=1
    left=right
print(sorted(set(r))[k-1])

### FIXED CODE ###

s=input()
k=int(input())
n=len(s)
r=[]
for right in range(0,n):
  for left in range(right+1, right+k+1):
    r.append(s[right:left])
print(sorted(set(r))[k-1])
### BUGGY CODE ###

import sys
import itertools
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
n=int(input())
a=input()


cnt=0
r=[]
g=[]
b=[]
def main():
	cnt=0
	for i in range(n):
		r_a=r.append
		b_a=b.append
		g_a=g.append
		if a[i]=="R":
			r_a(i)
		if a[i]=="B":
			b_a(i)
		if a[i]=="G":
			g_a(i)


	for i1 in r:
		for i2 in b:
			for i3 in g:
				if abs(i1-i2)==abs(i2-i3) or abs(i1-i3)==abs(i2-i3) or abs(i1-i3)==abs(i2-i1):
					cnt+=0
				else:
					cnt+=1
			
	print(cnt)
	
if __name__=="__main__":
	main()

### FIXED CODE ###

n=int(input())
s=input()
dic={}
cntr=0
cntg=0
cntb=0
for i in range(n):
    if s[i]=="R":
        dic[i]="R"
        cntr+=1
    if s[i]=="G":
        dic[i]="G"
        cntg+=1
    if s[i]=="B":
        dic[i]="B"
        cntb+=1

cnt=0
for i in range(0,n-2):
    for j in range(i+1,n-1):
        if 2*j-i<=n-1 and dic[i]!= dic[j]:
            if dic[i]!=dic[2*j-i] and dic[j]!=dic[2*j-i]:
                cnt+=1
print(cntr*cntg*cntb-cnt)
### BUGGY CODE ###

#ABC099C
N=int(input())
#1:6 2:36 3:216 4:1296 5:7776 6:46656 7:9 8:81 9:729 10:6561 11:59049
#dv=[6,36,216,1296,7776,46656,9,81,729,6561,59049]
lm=[6, 6, 6, 6, 6, 3, 9, 9, 9, 9, 2]
#ans=[0]*11
ans=0
sums=0
for i in range(lm[0]):
    for j in range(lm[1]):
        for k in range(lm[2]):
            for l in range(lm[3]):
                for m in range(lm[4]):
                    for n in range(lm[5]):
                        for o in range(lm[6]):
                            for p in range(lm[7]):
                                for q in range(lm[8]):
                                    for r in range(lm[9]):
                                        for s in range(lm[10]):
                                            sums=i*6+j*36+k*216+l*1296+m*7776+n*46656+o*9+p*81+q*729+r*6561+s*59049
                                            if N-sums>=0:
                                                ans_tmp=N-sums+i+j+k+l+m+n+o+p+q+r+s
                                                if ans_tmp<ans:
                                                    ans=ans_tmp
print(ans)

### FIXED CODE ###

#ABC099C
N=int(input())
i=0
t=0
ans=N
for i in range(N+1):
    nine = 0
    six = 0
    t=i
    while (t>0):
        nine+=t%9
        t//=9
    t=N-i
    while (t>0):
        six+=t%6
        t//=6
    if ans>nine+six:
        ans=nine+six
print(ans)
### BUGGY CODE ###

K , S = map(int , input().split())
cnt = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                cnt +=1

print(cnt)

### FIXED CODE ###

K , S = map(int , input().split())
cnt = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - (x + y)
        if 0 <= z <= K:
            cnt+=1

print(cnt)
### BUGGY CODE ###

[A,B,K]=list(map(int, input().split()))
for i in range (0,K):
    if A >= 1:
        A=A-1
    elif B >= 1:
        B=B-1
print(str(A)+" "+str(B))

### FIXED CODE ###

[A,B,K]=list(map(int, input().split()))
if A<=K:
    a=0
    if B<=K-A:
        B=0
    else:
        B=A+B-K
else:
    a=A-K
print(str(a)+" "+str(B))
### BUGGY CODE ###

n=int(input())
s=[[0] for _ in range(n)]
for i in range(n):
    s[i]=input()

ans=0
for p in range(n):
    cnt=0
    t=[[0] for _ in range(n)]
    for i in range(n):
        t[i]=s[(i+p)%n]
    for r in range(n):
        for l in range(n):
            if t[r][l]==t[l][r]:
                cnt+=1
    if cnt==n**2:
        ans+=1
print(ans*n)


### FIXED CODE ###

n=int(input())
s=[[0] for _ in range(n)]
for i in range(n):
    s[i]=input()

ans=0
for p in range(n):
    cnt=0
    t=[[0] for _ in range(n)]
    for i in range(n):
        t[i]=s[(i+p)%n]
    for r in range(n):
        for l in range(n):
            if t[r][l]==t[l][r]:
                cnt+=1
    if cnt==n**2:
        ans+=1
print(ans*n)
### BUGGY CODE ###

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


def solve():
    H, W = map(int, input().split())
    S = [[] for _ in range(H)]
    light = np.zeros((H, W), dtype='i8')
    for i in range(H):
        S[i] = list(input())

    for h in range(H):
        count = 0
        wr = -1
        for w in range(W):
            if S[h][w] == '.':
                if wr == -1:
                    wr = w
                count += 1
            elif S[h][w] == '#':
                if wr != -1:
                    light[h, wr:w] += count
                    wr = -1
                    count = 0
        else:
            if wr != -1:
                light[h, wr:w + 1] += count
                wr = -1
                count = 0

    for w in range(W):
        count = 0
        hr = -1
        for h in range(H):
            if S[h][w] == '.':
                if hr == -1:
                    hr = h
                count += 1
            elif S[h][w] == '#':
                if hr != -1:
                    light[hr:h, w] += count
                    hr = -1
                    count = 0
        else:
            if hr != -1:
                light[hr:h + 1, w] += count
                hr = -1
                count = 0

    print(np.max(light) - 1)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

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


def light_count(light, H, W, h, w, count, wr=-1, hr=-1):

    if wr != -1:
        for i in range(h * W + wr, h * W + w):
            light[i] += count
    elif hr != -1:
        for i in range(hr * W + w, h * W + w, W):
            light[i] += count


def solve():
    H, W = map(int, input().split())
    S = [[] for _ in range(H)]
    light = [0 for _ in range(H * W)]
    for i in range(H):
        S[i] = list(input())

    for h in range(H):
        count = 0
        wr = -1
        for w in range(W):
            if S[h][w] == '.':
                if wr == -1:
                    wr = w
                count += 1
            elif S[h][w] == '#':
                if wr != -1:
                    light_count(light, H, W, h, w, count, wr=wr)
                    wr = -1
                    count = 0
        else:
            if wr != -1:
                light_count(light, H, W, h, w + 1, count, wr=wr)
                wr = -1
                count = 0

    for w in range(W):
        count = 0
        hr = -1
        for h in range(H):
            if S[h][w] == '.':
                if hr == -1:
                    hr = h
                count += 1
            elif S[h][w] == '#':
                if hr != -1:
                    light_count(light, H, W, h, w, count, hr=hr)
                    hr = -1
                    count = 0
        else:
            if hr != -1:
                light_count(light, H, W, h + 1, w, count, hr=hr)
                hr = -1
                count = 0

    print(max(light) - 1)


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

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

ans =0
for i in range(N-1):
    for j in range(i+1,N):
            ans+=A[i]*A[j]

ans = ans % 1000000007
print(ans)

### FIXED CODE ###

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

ans =0
sum = sum(A)
for i in range(N-1):
    sum-=A[i]
    ans+=A[i]*sum

ans = ans % 1000000007
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
absort=sorted(ab,key=lambda x:(x[0],-x[1]))

ans=0
temp=[]
for i in range(1,m+1):
    while absort:
        if absort[0][0]<=i:
            temp.append(absort.pop(0))
        else:
            break
    temp=sorted(temp,key=lambda x:x[1], reverse=True)
    if temp:
        ans+=temp[0][1]
        temp.pop(0)

print(ans)


### FIXED CODE ###

import heapq

n,m = map(int,input().split())
ab=[[] for _ in range(m)]
for i in range(n):
    a,b=map(int,input().split())
    if a < m+1:
        ab[a-1].append(-b)

h=[]
ans=0
for i in range(m):
    for j in ab[i]:
        heapq.heappush(h,j)
    if len(h)==0:
        continue
    ans+=heapq.heappop(h)*(-1)
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a_l = list(map(int, input().split()))
a_l.sort(reverse=True)

total = 0
for i in range(n):
    total += a_l[i]

for i in range(m):    
    total -= (a_l[0]+1)//2
    a_l[0] //= 2
    for j in range(n-1):
        if a_l[j] >= a_l[j+1]:
            break
        else:
            a_l[j], a_l[j+1] = a_l[j+1], a_l[j]

print(total)

### FIXED CODE ###

n, m = map(int, input().split())
a_l = list(map(int, input().split()))
a_l.sort(reverse=True)

m_count = 0
while True:
    max_price = a_l[0]//2
    for j in range(n):
        if a_l[j] >= max_price:
            a_l[j] //= 2
            m_count += 1
            if m_count == m:
                break
        else:
            break
        if m_count == m:
            break
    a_l.sort(reverse=True)
    if m_count == m:
        break

ans = 0
for i in range(n):
    ans += a_l[i]
print(ans)
### BUGGY CODE ###

## coding: UTF-8
#memo:重なっている位置に爆弾があるかないかで、1こ増減することが考えられる
#import numpy as np

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

tate = [0] * H
yoko = [0] * W


bomb = set()
for i in range(M):
    hi, wi = map(int,input().split())
    tate[hi-1] += 1
    yoko[wi-1] += 1
    bomb.add((hi,wi))

#print(tate)
#print(yoko)
#print(bomb)
'''
tate_max = max(tate)
yoko_max = max(yoko)
index_tate = [i for i, v in enumerate(tate) if v == tate_max]
index_yoko = [i for i, v in enumerate(yoko) if v == yoko_max]
'''
tate_max = 0
index_tate = []
for i, v in enumerate(tate):
    if(tate_max < v):
        tate_max = v
        index_tate = [i]
    elif(tate_max == v):
        index_tate.append(i)
#print(tate_max, index_tate)

yoko_max = 0
index_yoko = []
for i, v in enumerate(yoko):
    if(yoko_max < v):
        yoko_max = v
        index_yoko = [i]
    elif(yoko_max == v):
        index_yoko.append(i)
#print(yoko_max, index_yoko)


#print(index_tate, index_yoko)

dammy = True
#1子でも「そこにない」ものがあれば、そのまま加算、そうでなければ、1こ引く
there_is = True
for i in index_tate:
    for j in index_yoko:
        #print(i+1, j+1)
        if((i+1, j+1) in bomb):
            dammy = True
        else:
            there_is = False

if(there_is):
    print(tate_max + yoko_max - 1)
else:
    print(tate_max + yoko_max)


        




'''
#tate_max = [i for i, v in enumerate(tate) if v == max(tate)]
np_list_tate = np.array(tate)
np_list_yoko = np.array(yoko)
tate_max = np_list_tate.argmax()
yoko_max = np_list_yoko.argmax()
print(tate_max, yoko_max)
'''

### FIXED CODE ###

## coding: UTF-8
#memo:重なっている位置に爆弾があるかないかで、1こ増減することが考えられる
#import numpy as np

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

tate = [0] * H
yoko = [0] * W


bomb = set()
for i in range(M):
    hi, wi = map(int,input().split())
    tate[hi-1] += 1
    yoko[wi-1] += 1
    bomb.add((hi,wi))
    

#print(tate)
#print(yoko)
#print(bomb)
'''
tate_max = max(tate)
yoko_max = max(yoko)
index_tate = [i for i, v in enumerate(tate) if v == tate_max]
index_yoko = [i for i, v in enumerate(yoko) if v == yoko_max]
'''
tate_max = 0
index_tate = []
for i, v in enumerate(tate):
    if(tate_max < v):
        tate_max = v
        index_tate = [i]
    elif(tate_max == v):
        index_tate.append(i)
#print(tate_max, index_tate)

yoko_max = 0
index_yoko = []
for i, v in enumerate(yoko):
    if(yoko_max < v):
        yoko_max = v
        index_yoko = [i]
    elif(yoko_max == v):
        index_yoko.append(i)
#print(yoko_max, index_yoko)


#print(index_tate, index_yoko)

dammy = True
#1子でも「そこにない」ものがあれば、そのまま加算、そうでなければ、1こ引く
there_is = True
flg = False
for i in index_tate:
    for j in index_yoko:
        #print(i+1, j+1)
        if((i+1, j+1) in bomb):
            dammy = True
        else:
            there_is = False
            flg = True
            break
    if flg:
        break

if(there_is):
    print(tate_max + yoko_max - 1)
else:
    print(tate_max + yoko_max)


        




'''
#tate_max = [i for i, v in enumerate(tate) if v == max(tate)]
np_list_tate = np.array(tate)
np_list_yoko = np.array(yoko)
tate_max = np_list_tate.argmax()
yoko_max = np_list_yoko.argmax()
print(tate_max, yoko_max)
'''
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = map(int,input().split())
    E = []
    S = 1
    for _ in range(m):
        u, v, a, b = map(int,input().split())
        u -= 1; v -= 1
        E.append((u, v, -a, b)) # a : cost of silver
        S += a
    for v in range(n):
        c, d = map(int,input().split()) # c : earning silver
        E.append((v, v, c, d))

    dp = [[INF] * S for _ in range(n)]
    dp[0][min(s, S - 1)] = 0

    # 基本的には Bellman - Ford で確定
    for _ in range(2 * n - 2):
        for u, v, ds, dt in E:
            for s in range(S):
                ns = s + ds
                if not (0 <= ns < S):
                    continue
                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)
                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)

    for i in range(1, n):
        print(min(dp[i][j] for j in range(S)))
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = map(int,input().split())
    E = [None] * m
    S = 0
    for i in range(m):
        u, v, a, b = map(int,input().split())
        S += a
        E[i] = (u - 1, v - 1, -a, b)

    exchange = [tuple(map(int,input().split())) for _ in range(n)]
    dp = [[INF] * (S + 1) for _ in range(n)]
    dp[0][min(s, S)] = 0

    for _ in range(2 * n - 3):
        # 先に両替を済ませる
        for v in range(n):
            for s in range(S + 1):
                ds, dt = exchange[v]
                dp[v][min(s + ds, S)] = min(dp[v][min(s + ds, S)], dp[v][s] + dt)
        # 移動する
        for u, v, ds, dt in E:
            for s in range(S + 1):
                ns = s + ds
                if ns < 0:
                    continue
                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)
                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)

    for v in range(1, n):
        print(min(dp[v][j] for j in range(S + 1)))
resolve()
### BUGGY CODE ###

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


### FIXED CODE ###

n,k = map(int,input().split())
arr = [0 for i in range(1,10**5+2)]
s = 0
for i in range(n):
    a,b = map(int, input().split())
    arr[a] += b
for i in range(1,10**5+1):
    s += arr[i]
    if k <= s:
        print(i)
        break
### BUGGY CODE ###

while 1:
	n=input()
	if n==0:break
	h=[0 for i in range(7)]
	for i in range(n):
		h[min(6,input()/10)]+=1
	for i in h:print i

### FIXED CODE ###

while 1:
	n=int(raw_input())
	if n==0:break
	h=[0 for i in range(7)]
	for i in range(n):
		h[min(6,int(raw_input())/10)] += 1
	for i in h:print i
### BUGGY CODE ###

import itertools
n = int(input())
a = list(map(int, input().split()))
ans = 0
p = 10 ** 9+7
for j in itertools.combinations(a,2):
    ans += (j[0]* j[1])%p
print(ans %p)

### FIXED CODE ###

import itertools
n = int(input())
a = list(map(int, input().split()))
suma = sum(a)-a[0]
ans = 0
p = 10 ** 9+7
for i in range(len(a)-1):
    ans += a[i]*suma
    suma -= a[i+1]
    ans = ans%p
print(ans)