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

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

total = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        total += ((A[i] % 1000000007) * (A[j] % 1000000007)) % 1000000007
print(total % 1000000007)


### FIXED CODE ###

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

mod = 10 ** 9 + 7

sum_a=0
for i in A:
    sum_a+=i
    sum_a%=mod

total=0
for i in range(N - 1):
    sum_a -= A[i]
    total+=A[i]*(sum_a)
    total%=mod
print(total)
### BUGGY CODE ###

from math import gcd

k = int(input())
ans = 0
 
for i in range(k):
  for j in range(k):
    for l in range(k):
      ans += gcd(gcd(i+1, j+1),l+1)
      
print(ans) 

### FIXED CODE ###

from math import gcd
k = int(input()) + 1
ans = 0
for i in range(1,k):
  for j in range(1,k):
    for l in range(1,k):
      ans += gcd(gcd(i, j),l)
print(ans)
### BUGGY CODE ###

x,y = map(int,input().split())

if x == y:
     print('-1')
else:
     i = 2 
     while True:
          if x*i == y:
               i += 1     
               continue
          elif x*i % y == 0:
               i += 1     
               continue
          else:
               print(x*i)
               break 

### FIXED CODE ###

x,y = map(int,input().split())


if x%y == 0:
     print('-1')
else:
     i = 2 
     while True:
          if x*i % y == 0:
               i += 1     
               continue
          else:
               print(x*i)
               break
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    ans = 0
    l, r = map(int, input().split())
    tar = S[l-1:r]
    tar = tar.replace('AC', '@')
    print(tar.count('@'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
imosu = [0] * (N + 1)
for i in range(N):
    imosu[i + 1] = imosu[i] + (1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(imosu[r-1]-imosu[l-1])
### BUGGY CODE ###

from itertools import product
import sys
input = sys.stdin.readline

X, Y, Z, K = map(int, input().split())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
C = [int(_) for _ in input().split()]
A = sorted(A)[::-1]
B = sorted(B)[::-1]
C = sorted(C)[::-1]

cnt = 0
Ax = 0
Bx = 0
Cx = 0
while cnt <= K:
    if Ax < X-1:
        a = A[Ax]-A[Ax+1]
    else:
        a = float('inf')
    if Bx < Y-1:
        b = B[Bx]-B[Bx+1]
    else:
        b = float('inf')
    if Cx < Z-1:
        c = C[Cx]-C[Cx+1]
    else:
        c = float('inf')
    if a <= b and a <= c:
        Ax += 1
    elif b <= a and b <= c:
        Bx += 1
    else:
        Cx += 1
    cnt += 1

List = []
for i, j, k in product(A[:Ax+1], B[:Bx+1], C[:Cx+1]):
    List.append(i+j+k)

List = sorted(List)[::-1]

for i in range(K):
    print(List[i])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
C = [int(_) for _ in input().split()]
A = sorted(A)[::-1]
B = sorted(B)[::-1]
C = sorted(C)[::-1]

List = []

for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1) > K:
                break
            else:
                List.append(A[i]+B[j]+C[k])

List = sorted(List)[-1:-K-1:-1]
for i in range(K):
    print(List[i])
### BUGGY CODE ###

import bisect

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
L = [list(map(int,input().split())) for i in range(M)]
L = sorted(L, key=lambda x: x[1], reverse=False)

for i in range(M) :
    b,c = L[i]
    
    bi = bisect.bisect(A,c)
    
    K = min(b,bi)
    #print(K,[b,bi])
    A = [c]*K + A[K:]
    A = sorted(A)
    #print(A)
print(sum(A))

### FIXED CODE ###

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

P = sorted(([[1,A[i]] for i in range(N)] + L),key=lambda x: x[1],reverse=True)

ans = 0
rest = N

for cost,value in P :
    K = min(cost, rest)
    K = max(0,K)
    ans += K * value
    rest -= cost

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

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

# input
n = int(input())
a_list = []
a_dic = {}
for ai in input().split():
    int_ai = int(ai)
    a_list.append(int_ai)
    if int_ai in a_dic:
        a_dic[int_ai] += 1
    else:
        a_dic[int_ai] = 1

a_solution_dic = {}
a_solution_dic_at_k = {}
for key in a_dic:
    if a_dic[key] == 1:
        continue
    a_solution_dic[key] = int(a_dic[key] * (a_dic[key]-1) / 2)
    #a_solution_dic_at_k[key] = int((a_dic[key]-1) * (a_dic[key]-2) / 2)


for k, ak in enumerate(a_list):
    sum_select = 0
    if a_dic[ak] <= 2:
        pass
    else:
        sum_select += int((a_dic[ak]-1) * (a_dic[ak]-2) / 2)
    for key in a_solution_dic:
        if key != ak:
            if a_dic[key] == 1:
                pass
            else:
                sum_select += a_solution_dic[key]


    print(sum_select)


### FIXED CODE ###

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

# input
n = int(input())
a_list = []
a_dic = {}
for ai in input().split():
    int_ai = int(ai)
    a_list.append(int_ai)
    if int_ai in a_dic:
        a_dic[int_ai] += 1
    else:
        a_dic[int_ai] = 1

a_solution_dic = {}
all_sum_select = 0
for key in list(a_dic.keys()):
    all_sum_select += int(a_dic[key] * (a_dic[key]-1) / 2)
    #a_solution_dic_at_k[key] = int((a_dic[key]-1) * (a_dic[key]-2) / 2)

for k, ak in enumerate(a_list):
    sum_select_at_k = all_sum_select + int((a_dic[ak]-1) * (a_dic[ak]-2) / 2) \
                       - int(a_dic[ak] * (a_dic[ak]-1) / 2)


    print(sum_select_at_k)
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split(" ")))

L.sort()

num_triangles = 0
for i in range(N-2): # stick 1
    for j in range(i+1, N-1): # stick 2; must be larger than 1
        # if a<b then we require c<b+a
        idx = bisect_left(a=L, x=L[i]+L[j], lo=j+1) # find the index at which c<b+a
        num_triangles += max(0, idx-(j+1)) # c can be, at minimum, b=c
print(num_triangles)


### FIXED CODE ###

from bisect import bisect_left

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

ans = 0
for i in range(n):
    for j in range(i+1, n):
        endpt = bisect_left(l, l[i] + l[j])
        ans += endpt-j-1

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

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

count = n

right_shakutori = [0] 
left_shakutori = [0] 

for i in range(len(a)):
    right_shakutori.append(right_shakutori[i] + a[i])
    left_shakutori.append(left_shakutori[i] ^ a[i])

for l in range(0, n):
    left = a[l]
    for r in range(l + 1,n):

        right = right_shakutori[r+1] - right_shakutori[l]

        left = left_shakutori[r+1] ^ left_shakutori[l]

        if right == left:
            count += 1
print(count)







### FIXED CODE ###

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

count = 0

xor_temp = 0
sum_temp = 0

r = 0
for l in range(n):
    while r < n and xor_temp^a[r]  == sum_temp + a[r]:
        xor_temp ^= a[r]
        sum_temp += a[r]
        r += 1

    xor_temp ^= a[l]
    sum_temp -= a[l]
    count += r - l

print(count)
### BUGGY CODE ###

N, K = [int(nk) for nk in input().split()]
A = [int(a) for a in input().split()]

A_set = list(set(A))
if len(A_set) <= K:
  print(0)
else:
  AA = [A.count(i) for i in A_set]
  AA.sort(reverse=True)
  ans = sum(AA[K:])
  print(ans)

### FIXED CODE ###

N, K = [int(nk) for nk in input().split()]
A = [int(a) for a in input().split()]

A_set = list(set(A))
if len(A_set) <= K:
  print(0)
else: # len(A_set) > K:
  dictionary = {}
  for n in A_set:
    dictionary[n] = 0
  for m in A:
    dictionary[m] += 1
  
  dict_val = list(dictionary.values())
  dict_val.sort(reverse = True)
  ans = N - sum(dict_val[:K])
  print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(lambda x: (int(x)+1)/2,input().split()))
ans=[]
for i in range(N-K+1):
    ans.append(sum(p[i:i+K]))
print(max(ans))

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(lambda x: int(x)+1,input().split()))
ans = sum(p[0:K])
s = ans
for i in range(1,N-K+1):
    s += p[i+K-1]-p[i-1]
    ans = max(ans,s)
print(ans/2)
### BUGGY CODE ###

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

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L].append((R, D))
    G[R].append((L, -D))


def dfs(v):
    visited[v] = True
    for u, d in G[v]:
        if dist[u] == float('inf'):
            dist[u] = dist[v] + d
        elif dist[u] != dist[v] + d:
            print('No')
            exit()
        if not visited[u]:
            dfs(u)


dist = []
visited = [False] * N
for v in range(N):
    if not visited[v]:
        dist = [float('inf')] * N
        dist[v] = 0
        dfs(v)
print('Yes')


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L].append((R, D))
    G[R].append((L, -D))

visited = [False] * N
dist = [float('inf')] * N
for i in range(N):
    if not visited[i]:
        dist[i] = 0
        stack = [i]
        while stack:
            v = stack.pop()
            visited[v] = True
            for u, d in G[v]:
                if dist[u] == float('inf'):
                    dist[u] = dist[v] + d
                elif dist[u] != dist[v] + d:
                    print('No')
                    exit()
                if not visited[u]:
                    stack.append(u)
print('Yes')
### BUGGY CODE ###

import numpy as np
N = int(input())
S = [input() for __ in range(N)]

S = np.array(S)
keys = set(S)
ans = {}
cnt = 0
ls = []
for key in keys:
    ans[key] = len(np.where(S == key)[0])

max_v = max(ans.values())
keys = [k for k, v in ans.items() if v == max_v]
keys.sort()
for key in keys:
    print(key)

### FIXED CODE ###

N = int(input())
d = {}
for i in range(N):
    S = input()
    if S in d.keys():
        d[S] = d[S] + 1
    else:
        d[S] = 1
max_val = max(d.values())
max_k_ls = [kv[0] for kv in d.items() if kv[1]==max_val]
max_k_ls = sorted(max_k_ls)

print(*max_k_ls, sep="\n")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

A = [list(map(int,input().split())) for i in range(H)]
B = [list(map(int,input().split())) for i in range(H)]

C = [[0]*W for i in range(H)]
M = 0

for h in range(H):
    for w in range(W):
        C[h][w] = abs(A[h][w] - B[h][w])
        M = max(M,C[h][w])
        
#print(C)

ZZZ = M*(H+W-1)+1

DP = [[[0]*ZZZ for i in range(W)] for j in range(H)]

for h in range(H):
    for w in range(W):
        if h==0 and w==0:
            DP[h][w][C[h][w]] = 1
        elif h==0:
            for i in range(ZZZ):
                DP[h][w][i] = DP[h][w-1][abs(i-C[h][w])]| (DP[h][w-1][abs(i+C[h][w])] if abs(i+C[h][w])<ZZZ else 0)
        elif w==0:
            for i in range(ZZZ):
                DP[h][w][i] = DP[h-1][w][abs(i-C[h][w])]|(DP[h-1][w][abs(i+C[h][w])] if abs(i+C[h][w])<ZZZ else 0)
        else:
            for i in range(ZZZ):
                DP[h][w][i] = DP[h-1][w][abs(i-C[h][w])]|(DP[h-1][w][abs(i+C[h][w])] if abs(i+C[h][w])<ZZZ else 0)|DP[h][w-1][abs(i-C[h][w])]|(DP[h][w-1][abs(i+C[h][w])] if abs(i+C[h][w])<ZZZ else 0)
                
for i in range(ZZZ):
    if DP[H-1][W-1][i]==1:
        ans = i
        break
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

A = [list(map(int,input().split())) for i in range(H)]
B = [list(map(int,input().split())) for i in range(H)]

C = [[0]*W for i in range(H)]
M = 0

for h in range(H):
    for w in range(W):
        C[h][w] = abs(A[h][w] - B[h][w])
        
#print(C)

c = 80*(H+W-1)+1

DP = [[0]*W for j in range(H)]

for h in range(H):
    for w in range(W):
        if h==0 and w==0:
            DP[h][w] = 1 << (C[h][w]+c)
        elif h==0:
            DP[h][w] = (DP[h][w-1] << C[h][w]) | (DP[h][w-1] >> C[h][w])
        elif w==0:
            DP[h][w] = (DP[h-1][w] << C[h][w]) | (DP[h-1][w] >> C[h][w])
        else:
            DP[h][w] = (DP[h][w-1] << C[h][w]) | (DP[h][w-1] >> C[h][w]) | (DP[h-1][w] << C[h][w]) | (DP[h-1][w] >> C[h][w])

ans = float('inf')
now = DP[H-1][W-1]
tmpans = -c
while now != 0:
    if now%2==1:
        ans = min(ans,abs(tmpans))
    tmpans += 1
    now = now >> 1

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

def solve():
    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp[vRem] = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        for v in reversed(range(vRem)):
            dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
        ans = min(ans, dp[0])

    print(ans)


solve()


### FIXED CODE ###

def solve():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp[vRem] = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        for v in reversed(range(vRem)):
            dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
        ans = min(ans, dp[0])

    print(ans)


solve()
### BUGGY CODE ###

n=int(input())
s=list(map(int,input().split()))
for i in range(n):
  print(s.count(i+1))

### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
k=[0]*n
for i in s:
  k[i-1]+=1
for i in k:
  print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod = 998244353

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

dp = [[[0]*3 for __ in range(S+1)] for _ in range(N+1)]
###dp[i][j][k]:Aのindex[i-1]まで見て和がjになっているもの
###kの意味は解説の通り


dp[0][0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][0] %= mod

        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][1] %= mod

        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        dp[i+1][j][2] %= mod

        if j+A[i] <= S:
            dp[i+1][j+A[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][1] %= mod
        
            dp[i+1][j+A[i]][2] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][2] %= mod

print(dp[N][S][2])

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 998244353

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

dp0 = [[0]*(S+1) for _ in range(N+1)]
dp1 = [[0]*(S+1) for _ in range(N+1)]
dp2 = [[0]*(S+1) for _ in range(N+1)]
###dp[i][j][k]:Aのindex[i-1]まで見て和がjになっているもの
###kの意味は解説の通り


dp0[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp0[i+1][j] += dp0[i][j]
        dp0[i+1][j] %= mod

        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp1[i+1][j] %= mod

        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        dp2[i+1][j] %= mod

        if j+A[i] <= S:
            dp1[i+1][j+A[i]] += dp0[i][j] + dp1[i][j]
            dp1[i+1][j+A[i]] %= mod
        
            dp2[i+1][j+A[i]] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+A[i]] %= mod

print(dp2[N][S])
### BUGGY CODE ###

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

R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i+1)
    elif S[i] == 'G':
        G.append(i+1)
    elif S[i] == 'B':
        B.append(i+1)

cnt = 0
for r in R:
    for g in G:
        up = max(r, g)
        down = min(r, g)
        diff = up - down
        
        ng = []
        if up + diff <= N:
            ng.append(up+diff)
        if down-diff >= 1:
            ng.append(down-diff)
        if diff%2 == 0:
            ng.append(int(up-diff/2))
        chk = 0
        for i in ng:
            if S[i-1] == 'B':
                chk += 1
        cnt += len(B) - chk

print(cnt)


### FIXED CODE ###

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

R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i+1)
    elif S[i] == 'G':
        G.append(i+1)
    elif S[i] == 'B':
        B.append(i+1)

lenb = len(B)

cnt = 0
for r in R:
    for g in G:
        up = max(r, g)
        down = min(r, g)
        diff = up - down
        
        chk = 0
        if up + diff <= N:
            if S[up+diff-1] == 'B':
                chk += 1
        if down-diff >= 1:
            if S[down-diff-1] == 'B':
                chk += 1
        if diff%2 == 0:
            if S[int(up-diff/2-1)] == 'B':
                chk += 1
        cnt += lenb - chk

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

n = int(input().rstrip())
line = input().rstrip().split(' ')

a = []
d = [0] * n
for i in range(n):
    num = int(line[i])
    a.append(num)
    d[num - 1] += 1

ans_list = [0] * n
for i in range(n):
    ans_list[i] = int(d[i] * (d[i] - 1) / 2)

for i in range(n):
    ans = 0
    for j in range(n):
        if a[i] == j + 1:
            num = d[j] - 1
            ans += num * (num - 1) / 2
        else:
            ans += ans_list[j]
    
    print(int(ans))


### FIXED CODE ###

n = int(input().rstrip())
line = input().rstrip().split(' ')

a = []
d = [0] * n
for i in range(n):
    num = int(line[i])
    a.append(num)
    d[num - 1] += 1

ans_list = [0] * n
for i in range(n):
    ans_list[i] = int(d[i] * (d[i] - 1) / 2)

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

for i in range(n):
    ans = total

    ans -= ans_list[a[i] - 1]
    num = d[a[i] - 1] - 1
    ans += num * (num - 1) / 2

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

from collections import deque
h, w = map(int, input().split())

g = []
for _ in range(h):
    tmp = list(input())
    g.append(tmp)

dp = [[1000000 for _ in range(w)] for __ in range(h)]

dp[0][0] = 0
q = deque([(0, 0)])

while q:
    x, y = q.popleft()
    if x+1 < h:
        if g[x+1][y] != g[x][y]:
            dp[x+1][y] = min(dp[x+1][y], dp[x][y]+1)
        else:
            dp[x+1][y] = min(dp[x+1][y], dp[x][y])
        q.append((x+1, y))
    if y+1 < w:
        if g[x][y+1] != g[x][y]:
            dp[x][y+1] = min(dp[x][y+1], dp[x][y]+1)
        else:
            dp[x][y+1] = min(dp[x][y+1], dp[x][y])
        q.append((x, y+1))

if g[0][0] == '.' and g[h-1][w-1] == '.':
    print(dp[h-1][w-1]//2)
elif g[0][0] != g[h-1][w-1]:
    print((dp[h-1][w-1]+1)//2)
else:
    print(1 + (dp[h-1][w-1]//2))

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())

g = []
for _ in range(h):
    tmp = list(input())
    g.append(tmp)

dp = [[1000000 for _ in range(w)] for __ in range(h)]

dp[0][0] = 0
# q = deque([(0, 0)])

# while q:
#     x, y = q.popleft()
#     if x+1 < h:
#         if g[x+1][y] != g[x][y]:
#             dp[x+1][y] = min(dp[x+1][y], dp[x][y]+1)
#         else:
#             dp[x+1][y] = min(dp[x+1][y], dp[x][y])
#         q.append((x+1, y))
#     if y+1 < w:
#         if g[x][y+1] != g[x][y]:
#             dp[x][y+1] = min(dp[x][y+1], dp[x][y]+1)
#         else:
#             dp[x][y+1] = min(dp[x][y+1], dp[x][y])
#         q.append((x, y+1))

for i in range(h):
    for j in range(w):
        if i == 0 and j != 0:
            if g[i][j] != g[i][j-1]:
                dp[i][j] = dp[i][j-1] + 1
            else:
                dp[i][j] = dp[i][j-1]
        elif i != 0:
            if j == 0:
                if g[i][0] != g[i-1][0]:
                    dp[i][0] = dp[i-1][0] + 1
                else:
                    dp[i][0] = dp[i-1][0]
            else:
                if g[i][j] != g[i][j-1]:
                    dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
                else:
                    dp[i][j] = min(dp[i][j], dp[i][j-1])

                if g[i][j] != g[i-1][j]:
                    dp[i][j] = min(dp[i][j], dp[i-1][j]+1)
                else:
                    dp[i][j] = min(dp[i][j], dp[i-1][j])


if g[0][0] == '.' and g[h-1][w-1] == '.':
    print(dp[h-1][w-1]//2)
elif g[0][0] != g[h-1][w-1]:
    print((dp[h-1][w-1]+1)//2)
else:
    print(1 + (dp[h-1][w-1]//2))
### BUGGY CODE ###

N,K=map(int,input().split())
ans=[]
for n in range(N):
  A,B=map(int,input().split())
  for b in range(B):
    ans.append(A)
ans.sort()
print(ans[K-1])


### FIXED CODE ###

N,K=map(int,input().split())
ans={}
for n in range(N):
  a,b=map(int,input().split())
  if a in ans.keys():
    ans[a]+=b
  else:
    ans[a]=b
answer=sorted(ans.items(), key=lambda x:x[0])
count=0
for k in range(len(answer)):
  count+=answer[k][1]
  if count>=K:
    print(answer[k][0])
    break
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  
  def knapsack_price(single=True):
    V = sum(price_list)
    dp_max = W + 1
    dp = [dp_max] * (V+1)
    dp[0] = 0
    
    for i in range(N):
      if single:
        S = list(reversed(range(price_list[i], V+1)))
      else:
        S = list(range(price_list[i], V+1))
      for price in S:
        dp[price] = min(dp[price], dp[price - price_list[i]] + weight_list[i])
    
    return max(price for price in range(V+1) if dp[price] <= W)
  
  N,W = map(int,input().split())
  
  price_list = []
  weight_list = []
  for _ in range(N):
    weight, price = map(int,input().split())
    price_list.append(price)
    weight_list.append(weight)
    
  print(knapsack_price(single=True))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  
  def knapsack_price(single=True):
    V = sum(price_list)
    dp_max = W + 1
    dp = [dp_max] * (V+1)
    dp[0] = 0
    
    for i in range(N):
      if single:
        S = list(reversed(range(price_list[i], V+1)))
      else:
        S = list(range(price_list[i], V+1))
      for price in S:
        dp[price] = min(dp[price], dp[price - price_list[i]] + weight_list[i])
    
    return max(price for price in range(V+1) if dp[price] <= W)
  
  N,W = map(int,input().split())
  
  price_list = []
  weight_list = []
  for _ in range(N):
    weight, price = map(int,input().split())
    price_list.append(price)
    weight_list.append(weight)
    
  print(knapsack_price(single=True))

if __name__ == '__main__':
    main()