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

import heapq

COST_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
fare_adj = [[COST_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
fare_sum = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_sum += a
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    exchanges.append((c, d))


mintime = [[TIME_MAX] * (fare_sum + 1) for _ in range(N)]


def search():
    q = [(0, 0, S)]
    while q:
        t, loc, silvers = heapq.heappop(q)
        silvers = min(silvers, fare_sum)
        if t >= mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        while silvers <= fare_sum:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = min(silvers - fare_adj[loc][nloc], fare_sum)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    heapq.heappush(q, (ntime, nloc, nsilvers))
            rate, wait = exchanges[loc]
            t += wait
            silvers += rate


search()
for t in range(1, N):
    print(min(mintime[t]))


### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline

NCOSTS = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
adj = [[] for _ in range(N * NCOSTS)]
fare_adj = [[NCOSTS] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0


def node(city, silvers):
    return silvers * N + city


for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for j in range(a, NCOSTS):
        adj[node(u, j)].append((node(v, j - a), b))
        adj[node(v, j)].append((node(u, j - a), b))

for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    for j in range(NCOSTS - c):
        adj[node(i, j)].append((node(i, j + c), d))


mintime = [TIME_MAX for _ in range(N * NCOSTS)]


def search():
    q = [(0, node(0, min(S, NCOSTS - 1)))]
    while q:
        t, node1 = heapq.heappop(q)
        if t > mintime[node1]:
            continue
        for node2, cost in adj[node1]:
            ntime = t + cost
            if mintime[node2] > ntime:
                mintime[node2] = ntime
                heapq.heappush(q, (ntime, node2))


search()
for i in range(1, N):
    print(min(mintime[node(i, j)] for j in range(NCOSTS)))
### BUGGY CODE ###

n = int(input())
a = 0
for i in range(n+1):
    if (str(i).count('7') + str(i).count('5') + str(i).count('3')) == len(str(i)):
        if '7' in str(i) and '5' in str(i) and '3' in str(i):
            a = a+1
print(a)

### FIXED CODE ###

n = int(input())
def dfs(s):
        if int(s) > n:
                return 0
        ret = 0
        if s.count('7')>0 and s.count('5')>0 and s.count('3')>0:
            ret = 1
        for c in '753':
                ret += dfs(s + c)
        return ret
print(dfs('0'))
### BUGGY CODE ###

def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    n1 = mid - left
    n2 = right - mid
    SENTINEL = max(S)+1
    L = S[left:mid]+[SENTINEL]
    R = S[mid:right]+[SENTINEL]
    i = 0
    j = 0
    c = 0
    for k in range(left, right):
        c += 1
        if L[i]<=R[j]:
            S[k] = L[i]
            i += 1
        else:
            S[k] = R[j]
            j += 1
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
for e in S:
    print e,
print
print c

### FIXED CODE ###

def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c
### BUGGY CODE ###

import math
N=int(input())
ans=0
for a in range(1,N+1):
    for b in range(1,N+1):
        for c in range(1,N+1):
            ans+=math.gcd(math.gcd(a,b),c)
print(ans)

### FIXED CODE ###

import math
N=int(input())
g1=[math.gcd(x,y) for x in range(1,N+1) for y in range(1,N+1)]
g2=[math.gcd(x,y) for x in g1 for y in range(1,N+1)]
print(sum(g2))
### BUGGY CODE ###

from math import ceil

n, a, b = map(int, input().split())
hs = [int(input()) for _ in range(n)]


def defeatable(k):
    hb = [max([h - k * b, 0]) for h in hs]
    n_attack = sum([ceil(h / (a - b)) for h in hb])
    return n_attack <= k


l, r = 0, 10 ** 14

while r - l > 1:
    m = (l + r) // 2

    if defeatable(m):
        r = m
    else:
        l = m

print(r)



### FIXED CODE ###

from math import ceil

n, a, b = map(int, input().split())
hs = [int(input()) for _ in range(n)]


def defeatable(k):
    hb = [max([h - k * b, 0]) for h in hs]
    n_attack = sum([ceil(h / (a - b)) for h in hb])
    return n_attack <= k


l, r = 0, ceil(max(hs) / b)

while r - l > 1:
    m = (l + r) // 2

    if defeatable(m):
        r = m
    else:
        l = m

print(r)
### BUGGY CODE ###

from collections import deque

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

def is_prime(p, s):
    if(s % p == 0):
        return 1
    else:
        return 0


def str_num(s):
    return int(''.join(s))


tmp = deque()

n = len(s)
cnt = 0
for i in range(n):
    for j in range(i + 1, n + 1):
        cnt += is_prime(p, str_num(s[i:j]))
print(cnt)

### FIXED CODE ###


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


cnt = [0] * p
cnt[0] = 1
rem = 0
sum = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            sum += i + 1

else:
    for i in range(n):
        rem = (int(s[-i - 1]) * pow(10, i, p) + rem) % p
        sum += cnt[rem]
        cnt[rem] += 1

print(sum)
### BUGGY CODE ###

S=input()
N=int(input())
count=0
for _ in range(N):
    *Q,=input().split()
    if len(Q)==1:
        count+=1
    else:
        if (count+int(Q[1]))%2:
            S=Q[2]+S
        else:
            S=S+Q[2]
print(S[::-1] if count%2 else S)

### FIXED CODE ###

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

from collections import*
D=deque(S)
count=0
for _ in range(N):
    *Q,=input().split()
    if len(Q)==1:
        count+=1
    else:
        if (count+int(Q[1]))%2:
            D.appendleft(Q[2])
        else:
            D.append(Q[2])
ans=''.join(D)
print(ans[::-1] if count%2 else ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
N=int(input())
C=[int(input())]
for i in range(N-1):
  tmp=int(input())
  if tmp != C[-1]:
    C.append(tmp)
  
import collections
table=collections.defaultdict(list)
N=len(C)
dp=[0]*(N+1)
dp[N]=1
mod=10**9 + 7
for i,x in enumerate(C[::-1]):
  dp[N-1-i]=dp[N-i]
  for y in table[x]:
    dp[N-1-i]+=dp[y+1]
    dp[N-1-i]%=mod
  table[x].append(N-1-i)

print(dp[0])


### FIXED CODE ###

import sys
input=sys.stdin.readline
N=int(input())
C=[int(input())]
for i in range(N-1):
  tmp=int(input())
  if tmp != C[-1]:
    C.append(tmp)
  
import collections
table=collections.defaultdict(int)
N=len(C)
dp=[0]*(N+1)
dp[N]=1
mod=10**9 + 7
for i,x in enumerate(C[::-1]):
  dp[N-1-i]=dp[N-i] + table[x] 
  dp[N-1-i]%=mod
  table[x]+=dp[N-i]
print(dp[0])
### BUGGY CODE ###

n,x,y = map(int,input().split())
ans = [0 for i in range(n)]
for i in range(n):
    for j in range(i,n):
        ans[min(abs(i-j),(abs(i-(x-1))+1+abs(y-1-j)),(abs(i-(x-1))+1+abs(y-1-j)))] += 1
for i in range(1,n):
    print(ans[i])


### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*n
for i in range(n):
    for j in range(i,n):
        ans[min(j-i,(abs(i-(x-1))+1+abs(y-1-j)),(abs(i-(x-1))+1+abs(y-1-j)))] += 1
for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, S: str):
    r = []
    g = []
    b = []
 
    for i, x in enumerate(S):
        if x ==  "R":r.append(i)
        elif x =="G":g.append(i)
        else:b.append(i)

    r = np.array(r)
    g = np.array(g)
    b = np.array(b)
  
    sb = set(b)
    ans = 0
    for r_ in r:
        # rg
        for g_ in g[g>r_]:
            # rgb
            if (g_ + (g_ - r_)) in sb:
                ans -= 1
            # brg
            if (r_ - (g_ - r_)) in sb:
                ans -= 1
            # rbg
            if ((r_ + g_)/2) in sb:
                ans -= 1

        # gr
        for g_ in g[g<r_]:
            # grb
            if (r_ + (r_ - g_)) in sb:
                ans -= 1
            # bgr
            if (g_ - (r_ - g_)) in sb:
                ans -= 1
            # gbr
            if ((r_ + g_)/2) in sb:
                ans -= 1
    ans += len(b) * len(g) * len(r)
    print(ans)
  
    return
 
 
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)
 
if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, S: str):
    r = []
    g = []
    b = []
    rp = 0
    gp = 0
    bp = 0

    rsum = [0]*(N+1)
    bsum = [0]*(N+1)
    gsum = [0]*(N+1)

    for i, x in enumerate(S[::-1]):
        if x ==  "R":
            r.append(i)
            rp = 1
        elif x =="G":
            g.append(i)
            gp = 1
        else:
            b.append(i)
            bp = 1
        rsum[N-1-i] = rsum[N-1-i+1] + rp
        gsum[N-1-i] = gsum[N-1-i+1] + gp
        bsum[N-1-i] = bsum[N-1-i+1] + bp
        rp = 0
        gp = 0
        bp = 0
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if S[i] != S[j]:
                if j+j-i<N: k = S[j+j-i]
                else: k = ""
                if (S[i] == "R" and S[j] == "B") or (S[j] == "R" and S[i] == "B"):
                    ans += gsum[j] - (k=="G")*1
                elif (S[i] == "R" and S[j] == "G") or (S[j] == "R" and S[i] == "G"):
                    ans += bsum[j] - (k=="B")*1
                elif (S[i] == "G" and S[j] == "B") or (S[j] == "G" and S[i] == "B"):
                    ans += rsum[j] - (k=="R")*1
    

    print(ans)
  
    return
 
 
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
tmp = sum(p[:k])
ans = [tmp]
if n == k:
    ans_mae = ans[0]
    print((ans_mae+k)/2)
else:
    for i in range(1,n-k+1):
        tmp = tmp - p[i-1] + p[i+k-1]
        ans.append(tmp)
    print((max(ans)+k)/2)
### BUGGY CODE ###

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    B = list(set(A))
    B.sort()
    Boo = [True]*len(B)

    zero =  A.count(1)
    if A.count(1)>1:
        print(0)
        return
    if A.count(1)==1:
        print(1)
        return

    for i in range(len(B)):
        for j in range(i+1,len(B)):
            if Boo[j] and B[j] % B[i] == 0:
                Boo[j] = False

    cnt = 0
    for i in range(len(B)):
        if Boo[i] and A.count(B[i])==1:
            cnt += 1

    print(cnt)



if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    ZENBU = [False]*(10**6+4)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        temp = 2
        if ZENBU[B[i]]==False:
            while B[i]*temp < 1000002:
                ZENBU[B[i]*temp] = True
                temp+=1

    cnt = 0
    for i in range(lenb):
        if ZENBU[B[i]]==False and C[B[i]]==1:
            cnt += 1

    print(cnt)


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

n = int(input())
for i in range(1, n+1):
    ans = 0
    for x in range(1, n+1):
        x2 = x*x
        for y in range(1, n+1):
            y2 = y*y
            xy = x * y
            for z in range(1, n+1):
                if x2 + y2 + z*z + xy + y*z + z*x == i:
                    ans += 1
    print(ans)

### FIXED CODE ###

import math
n = int(input())
# ans = [0 for _ in range(n)]
ans = [0] * n

for x in range(1, int(math.sqrt(n+1))):
    x2 = x*x
    for y in range(1, int(math.sqrt(n+1))):
        y2 = y*y
        xy = x * y
        tmp = x2 + y2 + xy
        if tmp >= n:
            break
        for z in range(1, int(math.sqrt(n+1))):
            tmp2 = tmp + z*z + y*z + z*x
            if tmp2 > n:
                break
            try:
                ans[tmp2 - 1] += 1
                # print(x, y, z)
            except:
                pass
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

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

S = [0]
X = [0]
for a in A:
    S.append(S[-1] + a)
    X.append(X[-1] ^ a)

#print(A)
#print(S)
#print(X)

ans = N
for i in range(1,N+1):
    for j in range(i+1, N+1):
        #print((i,j), S[j]-S[i-1], X[j]^X[i-1])
        if S[j]-S[i-1]==X[j]^X[i-1]:
            ans += 1
print(ans)


### FIXED CODE ###

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

l = 0 # start index
r = 0 # end index + 1
S = 0 # sum of As
X = 0 # XOR sum of As

ans = 0
while l<N:
    if S==X and r<=N:
        if r<N:
            S += A[r]
            X ^= A[r]
        r += 1
    else:
        S -= A[l]
        X ^= A[l]
        ans += r - l - 1
        l += 1

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

N, M, Q = list(map(int, input().split(' ')))
st_ed = {}
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    st_ed[(l, r)] = st_ed.get((l, r), 0) + 1

memo_s = {}
# memo[(p, q)] = memo[(p, q-1)] + sum([st_ed.get((i, q), 0) for i in [1,2,3...p]])
def f(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    if not (p, q) in memo_s:
        temp = f(p, q - 1)
        for i in range(p, q + 1):
            temp += st_ed.get((i, q), 0)
        memo_s[(p, q)] = temp
    return memo_s[(p, q)]

memo = {}
for i in range(Q):  # 1e5
    p, q = list(map(int, input().split(' ')))
    if not (p, q) in memo:
        temp = f(p, q)
        memo[(p, q)] = temp
    print(memo[(p, q)])



### FIXED CODE ###

N, M, Q = list(map(int, input().split(' ')))
st_ed = {}
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    st_ed[(l, r)] = st_ed.get((l, r), 0) + 1

memo_g = {}
def g(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    if not (p, q) in memo_g:
        memo_g[(p, q)] = st_ed.get((p, q), 0) + g(p + 1, q)
    return memo_g[(p, q)]

memo_f = {}
# memo[(p, q)] = memo[(p, q-1)] + sum([st_ed.get((i, q), 0) for i in [1,2,3...p]])
def f(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    if not (p, q) in memo_f:
        temp = f(p, q - 1) + g(p, q)
        memo_f[(p, q)] = temp
    return memo_f[(p, q)]

memo = {}
for i in range(Q):  # 1e5
    p, q = list(map(int, input().split(' ')))
    if not (p, q) in memo:
        temp = f(p, q)
        memo[(p, q)] = temp
    print(memo[(p, q)])
### BUGGY CODE ###

import sys
from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 9876598765

def ddprint(x):
  if DBG:
    print(x)

n,m,l = inm()

distance = [ [BIG] * n for i in range(n) ]
hops = [ [(BIG,0)] * n for i in range(n) ]
for i in range(n):
  distance[i][i] = 0
  hops[i][i] = (0,0)

dst = [ [] for i in range(n) ]
for i in range(m):
  a,b,c = inm()
  a -= 1
  b -= 1
  if c>l:
    continue
  distance[a][b] = distance[b][a] = c
  dst[a].append(b)
  dst[b].append(a)

for i in range(n):
  d = (0,0)
  q = deque([ (x,(0,distance[i][x])) for x in dst[i] ])
  while len(q)>0:
    y,e = q.popleft()
    #ddprint("y {} e {} {}".format(y,e[0],e[1]))
    if e>=hops[i][y]:
      continue
    #ddprint("upd i {} y {}".format(i,y))
    hops[i][y] = e
    for f in dst[y]:
      ds = distance[y][f]
      #ddprint("y {} f {} ds {}".format(y,f,ds))
      if e[1]+ds > l:
        newd = (e[0]+1, ds)
      else:
        newd = (e[0], e[1]+ds)
      if newd < hops[i][f]:
        q.append((f,newd))

if DBG:
  for i in range(n):
    print(hops[i])

for i in range(n):
  for j in range(n):
    if hops[i][j][0] > BIG/2:
      hops[i][j] = (-1,0)

p = inn()
for i in range(p):
  s,t = inm()
  #ddprint("q {} s {} t {}".format(i,s,t))
  print(hops[s-1][t-1][0])


### FIXED CODE ###

import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 9999999999

def ddprint(x):
  if DBG:
    print(x)

def ws(dist):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j],
                              dist[i][k]+dist[k][j])

n,m,l = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

dist1 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist1[i][i] = 0
    for j,c in dst[i]:
        dist1[i][j] = c

ws(dist1)

dist2 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist2[i][i] = 0
    for j in range(n):
        if dist1[i][j] <= l:
            dist2[i][j] = 1

ws(dist2)

q = inn()
for i in range(q):
    s,t = inm()
    d = dist2[s-1][t-1]
    print(d-1 if d<BIG else -1)
### BUGGY CODE ###

from collections import defaultdict

h, w, m = map(int, input().split())

row_dict = defaultdict(int)
col_dict = defaultdict(int)
row_col_dict = defaultdict(list)
for _ in range(m):
    row, col = map(int, input().split())
    row_dict[row] += 1
    col_dict[col] += 1
    row_col_dict[row].append(col)

max_rows = [k for k, v in row_dict.items() if v == max(row_dict.values())]
max_cols = [k for k, v in col_dict.items() if v == max(col_dict.values())]
ans = 0

for row in max_rows:
    for col in max_cols:
        bom = row_dict[row] + col_dict[col]
        if col in row_col_dict[row]:
            bom -= 1
        ans = max(ans, bom)

print(ans)


### FIXED CODE ###

from collections import defaultdict

h, w, m = map(int, input().split())

row_dict = defaultdict(int)
col_dict = defaultdict(int)
row_col_dict = defaultdict(set)
for _ in range(m):
    row, col = map(int, input().split())
    row_dict[row] += 1
    col_dict[col] += 1
    row_col_dict[row].add(col)

max_row = max(row_dict.values())
max_col = max(col_dict.values())

max_rows = [k for k, v in row_dict.items() if v == max_row]
max_cols = [k for k, v in col_dict.items() if v == max_col]
ans = max_row + max_col - 1
flg = False
if ans < m:
    for row in max_rows:
        for col in max_cols:
            if not col in row_col_dict[row]:
                ans += 1
                flg = True
                break
        if flg:
            break

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

A, B, N = map(int, input().split())
f = [int(A*x/B) - (A * int(x/B)) for x in range(N+1)]
print(max(f))

### FIXED CODE ###

def f(a, b, x):
  return int(a*x/b) - (a*int(x/b))
A, B, N = map(int, input().split())
print(f(A, B, min(B-1, N)))
### BUGGY CODE ###

N, K = list(map(int, input().split()))
L = []
for i in range(N):
	a, b = list(map(int, input().split()))
	for j in range(b):
		L.append(a)
L = sorted(L)
print(L[K - 1])

### FIXED CODE ###

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

L = []
for i in range(100000):
	L.append(0)

for i in range(N):
	a, b = list(map(int, input().split()))
	L[a - 1] += b

sm = 0
for i in range(100000):
	sm += L[i]
	if sm >= K:
		print(i + 1)
		break
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
binA=[None]*n
for i in range(n):
  binA[i]=bin(A[i])[2:]
  
keta=[0]*60
for i in range(n):
  tar=binA[i]
  for j in range(len(tar)-1,-1,-1):
    if tar[j]=="1":
      keta[len(tar)-1-j]+=1

pair=[0]*60
for i in range(len(keta)):
  pair[i]=keta[i]*(len(A)-keta[i])
  
ans=0
mul=1
DIV=10**9+7
for i in range(len(pair)):
  ans+=pair[i]*mul
  ans%=DIV
  mul*=2
print(ans)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
binA=[None]*n
for i in range(n):
  binA[i]=bin(A[i])[2:]
  
keta=[0]*60
for i in range(n):
  tar=binA[i]
  for j in range(len(tar)-1,-1,-1):
    if tar[j]=="1":
      keta[len(tar)-1-j]+=1

pair=[0]*60
for i in range(len(keta)):
  pair[i]=keta[i]*(len(A)-keta[i])
  
ans=0
mul=1
DIV=10**9+7
for i in range(len(pair)):
  ans+=pair[i]*mul
  ans%=DIV
  mul*=2
print(ans)
### BUGGY CODE ###

import numpy as np

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
v_max = sum([i[1] for i in items])
INF = 10**12
dp = np.array([[INF for j in range(N * v_max+1)] for _ in range(N+1)])
dp[0, 0] = 0
for i in range(1, N+1):
    w, v = items[i-1]
    dp[i, :v] = dp[i-1, :v]
    dp[i, v:] = np.minimum(dp[i-1, :-v] + w, dp[i-1, v:])
ans = 0
for v in range(N * v_max, -1, -1):
    if dp[N][v] <= W:
        ans = v
        break
print(ans)

### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
v_max = sum([i[1] for i in items])
INF = 10**12
dp = np.array([[INF for j in range(v_max+1)] for _ in range(N+1)])
dp[0, 0] = 0
for i in range(1, N+1):
    w, v = items[i-1]
    dp[i, :v] = dp[i-1, :v]
    dp[i, v:] = np.minimum(dp[i-1, :-v] + w, dp[i-1, v:])
ans = 0
for v in range(v_max, -1, -1):
    if dp[N][v] <= W:
        ans = v
        break
print(ans)