Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math

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

d=[]
i=1
while math.sqrt(M)>=i:
    if M%i==0:
        d.append(i)
        if i**2!=M:
            d.append(M//i)
    i=i+1
d.sort()#Mの約数列

m=0
i=0
while  M//N>=d[i]:
    if M%d[i]==0:
        m=d[i]
    i=i+1
print(m)

Fixed submission:
import math

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

d=[]
i=1
while math.sqrt(M)>=i:
    if M%i==0:
        d.append(i)
        if i**2!=M:
            d.append(M//i)
    i=i+1
d.sort()#Mの約数列

m=0
i=0
while  len(d)-1>=i and M//N>=d[i]:
    if  M%d[i]==0:
        m=d[i]
    i=i+1
print(m)

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
m=0
i=1
while  M//N>=i:
    if M%i==0:
        m=i
    i=i+1
print(m)


Fixed submission:
import math

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

d=[]
i=1
while math.sqrt(M)>=i:
    if M%i==0:
        d.append(i)
        if i**2!=M:
            d.append(M//i)
    i=i+1
d.sort()#Mの約数列

m=0
i=0
while  len(d)-1>=i and M//N>=d[i]:
    if  M%d[i]==0:
        m=d[i]
    i=i+1
print(m)
Buggy python submission (verdict: Runtime Error):
from math import gcd
for i in range(int(input())):
    a,b,c,d=map(int,input().split())
    g=gcd(b,d)
    r=a%g
    if r>=b-d and c>=b-(g-r) and a>=b:
        print("Yes")
    else:
        print("No")


Fixed submission:
from fractions import gcd
for i in range(int(input())):
    a,b,c,d=map(int,input().split())
    g=gcd(b,d)
    r=a%g
    if r>=b-d and c>=b-(g-r) and a>=b:
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))

data=[((A[0],0),(-1,-1)) for i in range(2**N)]
for i in range(1,2**N):
    test=set([])
    for j in range(0,N):
        if i>>j&1==1:
            a,b=data[i-2**j]
            test.add(a)
            test.add(b)
    test.add((A[i],i))
    test=list(test)
    test.sort()
    data[i]=(test[-1],test[-2])

ans=[data[i][0][0]+data[i][1][0] for i in range(2**N)]
for i in range(2,2**N):
    ans[i]=max(ans[i],ans[i-1])

for i in range(1,2**N):
    print(ans[i])


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

data=[[(A[0],0),(-1,-1)] for i in range(2**N)]
for i in range(1,2**N):
    for j in range(N):
        if i>>j&1==1:
            a,b=data[i-2**j]
            if a[0]>data[i][0][0]:
                data[i][1]=data[i][0]
                data[i][0]=a
            elif a[0]>data[i][1][0] and a[1]!=data[i][0][1]:
                data[i][1]=a
            if b[0]>data[i][0][0]:
                data[i][1]=data[i][0]
                data[i][0]=b
            elif b[0]>data[i][1][0] and b[1]!=data[i][0][1]:
                data[i][1]=b
    a=(A[i],i)
    if a[0]>data[i][0][0]:
        data[i][1]=data[i][0]
        data[i][0]=a
    elif a[0]>data[i][1][0] and a[1]!=data[i][0][1]:
        data[i][1]=a


ans=[data[i][0][0]+data[i][1][0] for i in range(2**N)]
for i in range(2,2**N):
    ans[i]=max(ans[i],ans[i-1])

for i in range(1,2**N):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
edge=[set([]) for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    edge[a-1].add(b-1)
    edge[b-1].add(a-1)

cedge=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if j not in edge[i] and j!=i:
            cedge[i].append(j)

ans=[]
def is_bipartgraph():
    color=[0]*N
    used=[False]*N
    for i in range(N):
        if not used[i]:
            stack=[(i,1)]
            black=0
            white=0
            while stack:
                v,c=stack.pop()
                used[v]=True
                color[v]=c
                black+=(c==1)
                white+=(c==-1)
                for nv in cedge[v]:
                    if color[nv]==color[v]:
                        return False
                    elif color[nv]==0:
                        stack.append((nv,-c))
            ans.append([black,white])
    return True

if is_bipartgraph():
    dp=[[False for i in range(0,N+1)] for j in range(len(ans))]
    a,b=ans[0]
    dp[0][a],dp[0][b]=True,True
    for i in range(1,len(ans)):
        a,b=ans[i]
        for j in range(0,N+1):
            test=False
            if j>=a:
                test=test|dp[i-1][j-a]
            if j>=b:
                test=test|dp[i-1][j-b]
            dp[i][j]=test
    ans=0
    for i in range(0,N+1):
        if dp[-1][i] and abs(ans-N/2)>abs(i-N/2):
            ans=i
    ans2=N-ans
    print(ans*(ans-1)//2+ans2*(ans2-1)//2)
else:
    print(-1)

Fixed submission:
N,M=map(int,input().split())
edge=[set([]) for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    edge[a-1].add(b-1)
    edge[b-1].add(a-1)

cedge=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if j not in edge[i] and j!=i:
            cedge[i].append(j)

ans=[]
def is_bipartgraph():
    color=[0]*N
    used=[False]*N
    for i in range(N):
        if not used[i]:
            stack=[(i,1)]
            black=0
            white=0
            while stack:
                v,c=stack.pop()
                color[v]=c
                black+=(not used[v])*(c==1)
                white+=(not used[v])*(c==-1)
                used[v]=True
                for nv in cedge[v]:
                    if color[nv]==color[v]:
                        return False
                    elif color[nv]==0:
                        stack.append((nv,-c))
            ans.append([black,white])
    return True

if is_bipartgraph():
    dp=[[False for i in range(0,N+1)] for j in range(len(ans))]
    a,b=ans[0]
    dp[0][a],dp[0][b]=True,True
    for i in range(1,len(ans)):
        a,b=ans[i]
        for j in range(0,N+1):
            test=False
            if j>=a:
                test=test|dp[i-1][j-a]
            if j>=b:
                test=test|dp[i-1][j-b]
            dp[i][j]=test
    ans=0
    for i in range(0,N+1):
        if dp[-1][i] and abs(ans-N/2)>abs(i-N/2):
            ans=i
    ans2=N-ans
    print(ans*(ans-1)//2+ans2*(ans2-1)//2)
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
N,K,Q=map(int,input().split())
A=list(map(int,input().split()))
a=list(set(A))
a.sort()
ans=float("inf")
def condition(i,num):
    if i>a[num]:
        return False
    X=a[num]
    Y=A[i]
    data=[-1 for i in range(0,N)]
    for k in range(0,N):
        if Y>A[k]:
            data[k]=0
        elif A[k]>X:
            data[k]=1
        else:
            data[k]=2
    check=0
    stack=0
    count=0
    for k in range(0,N):
        if data[k]==1:
            stack+=1
        elif data[k]==2:
            stack+=1
            count+=1
        else:
            t=stack+1-K
            check+=max(min(t,count),0)
            stack=0
            count=0
    t=stack+1-K
    check+=max(min(t,count),0)
    return check>=Q

for i in range(0,N):
    start=0
    end=len(a)-1
    while end-start>1:
        test=(end+start)//2
        if condition(i,test):
            end=test
        else:
            start=test
    if condition(i,start):
        ans=min(ans,a[start]-A[i])
    elif condition(i,end):
        ans=min(ans,a[end]-A[i])
print(ans)

Fixed submission:
N,K,Q=map(int,input().split())
A=list(map(int,input().split()))
a=list(set(A))
a.sort()
ans=float("inf")
def condition(i,num):
    if i>a[num]:
        return False
    X=a[num]
    Y=A[i]
    check=0
    stack=0
    count=0
    for k in range(0,N):
        if A[k]>X:
            stack+=1
        elif A[k]>=Y:
            stack+=1
            count+=1
        else:
            t=stack+1-K
            check+=max(min(t,count),0)
            stack=0
            count=0
    t=stack+1-K
    check+=max(min(t,count),0)
    return check>=Q

for i in range(0,N):
    start=0
    end=len(a)-1
    while end-start>1:
        test=(end+start)//2
        if condition(i,test):
            end=test
        else:
            start=test
    if condition(i,start):
        ans=min(ans,a[start]-A[i])
    elif condition(i,end):
        ans=min(ans,a[end]-A[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=["" for j in range(N)]
for i in range(N):
    S[i]=input()

ans=0
for i in range(0,N):
    flag=True
    for j in range(0,N):
        for k in range(0,N):
            flag=flag&(S[(k+i)%N][j]==S[(j+i)%N][k])
    ans+=N*int(flag)

print(ans)


Fixed submission:
N=int(input())
S=["" for j in range(N)]
for i in range(N):
    S[i]=input()

ans=0
for i in range(0,N):
    flag=True
    for j in range(0,N):
        for k in range(0,N):
            flag=flag&(S[(k+i)%N][j]==S[(j+i)%N][k])
    ans+=N*int(flag)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=[["" for i in range(N)] for j in range(N)]
for i in range(N):
    s=input()
    for j in range(N):
        S[i][j]=s[j]

ans=0
for i in range(0,N):
    A,B=i,0
    flag=0
    for j in range(0,N):
        for k in range(0,N):
            if S[(k+A)%N][(j+B)%N]!=S[(j+A)%N][(k+B)%N]:
                flag=1
    if flag==0:
        ans+=N

print(ans)


Fixed submission:
N=int(input())
S=["" for j in range(N)]
for i in range(N):
    S[i]=input()

ans=0
for i in range(0,N):
    flag=True
    for j in range(0,N):
        for k in range(0,N):
            flag=flag&(S[(k+i)%N][j]==S[(j+i)%N][k])
    ans+=N*int(flag)

print(ans)
Buggy python submission (verdict: Runtime Error):
def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5
g1 = [1]*(N+1) # 元テーブル
g2 = [1]*(N+1) #逆元テーブル
inverse = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0

N,M=map(int,input().split())
A=[0]+list(map(int,input().split()))
start=time.time()
dp=[[0 for i in range(2**N)] for j in range(M+1)]

dp[0][0]=g1[2**N-1]

for i in range(1,M+1):
    for j in range(2**N):
        dp[i][j]=dp[i-1][j]
        for k in range(N):
            if j>>k &1==0 and 2**N-A[i]-j>=2**k-1:
                dp[i][j]=(dp[i][j]+((-1)*((g1[2**N-A[i]-j]*g2[2**N-A[i]+1-(j+2**k)])%mod)*((dp[i-1][j+2**k]+g1[2**N-1-j-2**k])*2**k)%mod)%mod)%mod

#for i in range(M+1):
    #print(dp[i])
print((dp[M][0]*pow(2,N,mod))%mod)


Fixed submission:
def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5
g1 = [1]*(N+1) # 元テーブル
g2 = [1]*(N+1) #逆元テーブル
inverse = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0

N,M=map(int,input().split())
A=[0]+list(map(int,input().split()))
dp=[[0 for i in range(2**N)] for j in range(M+1)]

dp[0][0]=g1[2**N-1]

for i in range(1,M+1):
    for j in range(2**N):
        dp[i][j]=dp[i-1][j]
        for k in range(N):
            if j>>k &1==0 and 2**N-A[i]-j>=2**k-1:
                dp[i][j]=(dp[i][j]+((-1)*((g1[2**N-A[i]-j]*g2[2**N-A[i]+1-(j+2**k)])%mod)*((dp[i-1][j+2**k]+g1[2**N-1-j-2**k])*2**k)%mod)%mod)%mod

#for i in range(M+1):
    #print(dp[i])
print((dp[M][0]*pow(2,N,mod))%mod)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10**7)

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

def condition(val):
    memo={}
    def dfs(num,count):
        if count>=val:
            return 0

        if (num,count) in memo:
            return memo[(num,count)]

        if num==N:
            memo[(num,count)]=int(val>count)
            return memo[(num,count)]

        ans=dfs(num+1,count+A[num])+dfs(num+1,count)
        memo[(num,count)]=ans
        return memo[(num,count)]

    return 2**(N-1)>dfs(0,0)-1

start=0
end=2000**2
while end-start>1:
    test=(start+end)//2
    if condition(test):
        start=test
    else:
        end=test

if condition(end):
    print(end)
else:
    print(start)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
if S%2==1:
    check=1
    for i in range(N):
        check=check|check<<A[i]
    for i in range(S//2+1,S+1):
        if check>>i &1==1:
            print(i)
            break
else:
    check=1
    for i in range(N):
        check=check|check<<A[i]

    for i in range(S//2,S+1):
        if check>>i &1==1:
            print(i)
            break
Buggy python submission (verdict: Runtime Error):
K=38
K=int(input())
N=K**2-K+1

print(N,K)
_res=[[-1 for j in range(K-1)] for i in range((K-1)**2)]
rest=[[-1 for j in range(K-1)] for i in range(K-1)]

id=K
start=0
while N>id:
    for j in range(K-1):
        _res[(K-1)*j+(start+j*((id-1)//(K-1)))%(K-1)][(id-1)//(K-1)-1]=id
    id+=1
    start=(start+1)%(K-1)

rest=[[_res[j][i] for j in range(K-1)] for i in range(K-1)]

ans=[[i for i in range(K)]]
for i in range(K-1):
    for j in range(K-1):
        tmp=[i]+_res[(K-1)*i+j]
        ans.append(tmp)
for i in range(K-1):
    tmp=[K-1]+rest[i]
    ans.append(tmp)

for i in range(N):
    ans[i]=[ans[i][j]+1 for j in range(K)]

for i in range(N):
    print(*ans[i])

def check():
    ids=[[] for i in range(N)]
    for i in range(N):
        ans[i].sort()
        if ans[i][0]<0 or ans[i][-1]>N-1:
            exit(print("WA1"))
        for j in range(1,K):
            if ans[i][j]==ans[i][j-1]:
                exit(print("WA2"))
        for j in range(K):
            ids[ans[i][j]].append(i)
    for i in range(N):
        if len(ids[i])!=K:
            exit(print("WA3"))
    p=set([])
    for i in range(N):
        for j in range(len(ids[i])):
            for k in range(j):
                a,b=ids[i][j],ids[i][k]
                if (a,b) in p:
                    print("WA4")
                    print(ans[a])
                    print(ans[b])
                    exit()

                p.add((a,b))

#check()


Fixed submission:
K=38
#K=int(input())
N=K**2-K+1

print(N,K)
_res=[[-1 for j in range(K-1)] for i in range((K-1)**2)]
rest=[[-1 for j in range(K-1)] for i in range(K-1)]

id=K
start=0
while N>id:
    for j in range(K-1):
        _res[(K-1)*j+(start+j*((id-1)//(K-1)))%(K-1)][(id-1)//(K-1)-1]=id
    id+=1
    start=(start+1)%(K-1)

rest=[[_res[j][i] for j in range(K-1)] for i in range(K-1)]

ans=[[i for i in range(K)]]
for i in range(K-1):
    for j in range(K-1):
        tmp=[i]+_res[(K-1)*i+j]
        ans.append(tmp)
for i in range(K-1):
    tmp=[K-1]+rest[i]
    ans.append(tmp)

for i in range(N):
    ans[i]=[ans[i][j]+1 for j in range(K)]

for i in range(N):
    print(*ans[i])

def check():
    ids=[[] for i in range(N)]
    for i in range(N):
        ans[i].sort()
        if ans[i][0]<0 or ans[i][-1]>N-1:
            exit(print("WA1"))
        for j in range(1,K):
            if ans[i][j]==ans[i][j-1]:
                exit(print("WA2"))
        for j in range(K):
            ids[ans[i][j]].append(i)
    for i in range(N):
        if len(ids[i])!=K:
            exit(print("WA3"))
    p=set([])
    for i in range(N):
        for j in range(len(ids[i])):
            for k in range(j):
                a,b=ids[i][j],ids[i][k]
                if (a,b) in p:
                    print("WA4")
                    print(ans[a])
                    print(ans[b])
                    exit()

                p.add((a,b))

#check()
Buggy python submission (verdict: Time Limit Exceeded):
N,Z,W=map(int,input().split())
A=list(map(int,input().split()))
A.append(Z)
A.append(W)

dp=[[[0 for i in range(0,2)] for j in range(0,N+2)] for k in range(0,N+1)]

for i in range(0,N+2):
    dp[N-1][i][0]=abs(A[N-1]-A[i])
    dp[N-1][i][1]=abs(A[N-1]-A[i])


for i in range(1,N):
    for j in range(0,N+2):
        I=N-1-i
        dp[I][j][0]=max(dp[I+1][I][1],dp[I+1][j][0],abs(A[N-1]-A[j]))
        dp[I][j][1]=min(dp[I+1][I][0],dp[I+1][j][1],abs(A[N-1]-A[j]))

print(dp[0][N+1][0])

Fixed submission:
N,Z,W=map(int,input().split())
A=list(map(int,input().split()))
A.append(Z)
A.append(W)


dpx=[[0 for j in range(0,N+2)] for k in range(0,N+1)]
dpy=[[0 for j in range(0,N+2)] for k in range(0,N+1)]

for i in range(0,N+2):
    dpx[N-1][i]=abs(A[N-1]-A[i])
    dpy[N-1][i]=abs(A[N-1]-A[i])


for i in range(1,N):
    for j in range(0,N+2):
        I=N-1-i
        dpx[I][j]=max(dpy[I+1][I],dpx[I+1][j],abs(A[N-1]-A[j]))
        dpy[I][j]=min(dpx[I+1][I],dpy[I+1][j],abs(A[N-1]-A[j]))

print(dpx[0][N+1])
Buggy python submission (verdict: Time Limit Exceeded):
K=int(input())
a=K
while a%2==0:
    a//=2
while a%5==0:
    a//=5
if a==1:
    print(1)
else:
    mod=set([])
    a=1
    while a not in mod:
        mod.add(a)
        a*=10
        a%=K

    mod=list(mod)
    n=len(mod)
    check=1
    table=[0 for i in range(0,n)]
    for i in range(1,46):
        for j in range(0,n):
            table[j]=(check<<mod[j])|check
        ans=0
        for j in range(0,n):
            ans=ans|table[j]
        check=ans
        for j in range(1,46):
            if (check>>j*K)&1==1:
                print(i)
                exit()

Fixed submission:
K=int(input())
a=K
while a%2==0:
    a//=2
while a%5==0:
    a//=5
if a==1:
    print(1)
else:
    mod=set([])
    a=1
    while a not in mod:
        mod.add(a)
        a*=10
        a%=K

    mod=list(mod)
    n=len(mod)
    wei=pow(2,K)-1
    check=1
    ans=0
    for j in range(0,n):
        ans=ans|(check<<mod[j])
    check=ans
    for i in range(1,46):
        if check>>0 &1==1:
            print(i)
            exit()
        ans=check
        for j in range(0,n):
            ans=ans|(check<<mod[j])
        ans1=ans&wei
        ans2=ans>>K
        check=ans1|ans2

Buggy python submission (verdict: Runtime Error):
K=int(input())

if K%10==0:
    print(1)
else:
    mod=set([])
    i=0
    while pow(10,i,K) not in mod:
        mod.add(pow(10,i,K))
        i+=1

    mod=list(mod)
    mod.sort(reverse=True)

    ans=0
    for i in range(0,len(mod)):
        ans+=K//mod[i]
        K%=mod[i]

    print(ans)

Fixed submission:
K=int(input())
a=K
while a%2==0:
    a//=2
while a%5==0:
    a//=5
if a==1:
    print(1)
else:
    mod=set([])
    a=1
    while a not in mod:
        mod.add(a)
        a*=10
        a%=K

    mod=list(mod)
    n=len(mod)
    wei=pow(2,K)-1
    check=1
    ans=0
    for j in range(0,n):
        ans=ans|(check<<mod[j])
    check=ans
    for i in range(1,46):
        if check>>0 &1==1:
            print(i)
            exit()
        ans=check
        for j in range(0,n):
            ans=ans|(check<<mod[j])
        ans1=ans&wei
        ans2=ans>>K
        check=ans1|ans2
Buggy python submission (verdict: Time Limit Exceeded):
import sys

input=sys.stdin.readline

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

bit=[]
for i in range(0,30):
    if K>>i &1==1:
        bit.append(i)

ans=0
for j in range(N):
    test=0
    for j in range(N):
        a,b=integer[j]
        if a|K==K:
            test+=b
    ans=max(ans,test)

for i in bit:
    check=(K>>i)-1
    test=0
    for j in range(N):
        a,b=integer[j]
        if a>>i|check==check:
            test+=b
    ans=max(ans,test)

print(ans)

Fixed submission:
import sys

input=sys.stdin.readline

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

bit=[]
for i in range(0,30):
    if K>>i &1==1:
        bit.append(i)

ans=0
for j in range(N):
    a,b=integer[j]
    if a|K==K:
        ans+=b

for i in bit:
    check=(K>>i)-1
    test=0
    for j in range(N):
        a,b=integer[j]
        if a>>i|check==check:
            test+=b
    ans=max(ans,test)

print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
a =[]
for _ in range(0,N):
    a.append(input())
s=0
x=0
b=[0]*(10**9)
for i in range(0,N):
    x=int(a[i])
    if b[x]==0:
        b[x]=1
    else:
        b[x]=0
y=int(max(a))
for i in range(0,y):
    s=s+b[i]
print(s)

Fixed submission:
N=int(input())
a =[]
for _ in range(0,N):
    a.append(int(input()))
b =[]
f=0
s=0
a.sort()
for i in range(0,N):
    if i==0:
        b.append(1)
    elif a[i]==a[i-1]:
        if b[f]==1:
            b[f]=0
        else:
            b[f]=1
    else:
        b.append(1)
        f=f+1
for i in range(0,len(b)):
    s=s+b[i]
print(s)
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
a =[0]*N
b =[0]*N
for i in range(0,N):
    a[i],b[i] =map(int,input().split())
c=[0]*(10**6)
for i in range(0,N):
    c[a[i]]=c[a[i]]+b[i]
s=0
i=1
while s<K:
    s=s+c[i]
    x=a[i-1]
    i=i+1
print(x)

Fixed submission:
N,K=map(int,input().split())
a =[0]*N
b =[0]*N
for i in range(0,N):
    a[i],b[i] =map(int,input().split())
c=[0]*(10**6)
for i in range(0,N):
    c[a[i]]=c[a[i]]+b[i]
s=0
i=1
while s<K:
    s=s+c[i]
    x=i
    i=i+1
print(x)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
a =[0]*N
b =[0]*N
for i in range(0,N):
    a[i],b[i] =map(int,input().split())
s=0
t=0
A=0
while s<K:
    A=min(a)
    t=A
    s=s+b[a.index(A)]
    a[a.index(A)]=max(a)+A
print(t)

Fixed submission:
N,K=map(int,input().split())
a =[0]*N
b =[0]*N
for i in range(0,N):
    a[i],b[i] =map(int,input().split())
c=[0]*(10**6)
for i in range(0,N):
    c[a[i]]=c[a[i]]+b[i]
s=0
i=1
while s<K:
    s=s+c[i]
    x=i
    i=i+1
print(x)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
a =[0]*N
b =[0]*N
for i in range(0,N):
    a[i],b[i] =map(int,input().split())
a.sort()
c =[]
for i in range(0,N):
    for j in range(0,b[i]):
        c.append(a[i])
print(c[K-1])

Fixed submission:
N,K=map(int,input().split())
a =[0]*N
b =[0]*N
for i in range(0,N):
    a[i],b[i] =map(int,input().split())
c=[0]*(10**6)
for i in range(0,N):
    c[a[i]]=c[a[i]]+b[i]
s=0
i=1
while s<K:
    s=s+c[i]
    x=i
    i=i+1
print(x)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

H,W,K=map(int,input().split())
A=["" for i in range(H)]
for i in range(H):
    A[i]=input()

for i in range(H):
    for j in range(W):
        if A[i][j]=="S":
            s=(i,j)

move=[(0,1),(1,0),(0,-1),(-1,0)]
start=set([s])
que=[(0,s[0],s[1])]
heapq.heapify(que)
while que:
    count,posx,posy=heapq.heappop(que)
    if count==K:
        continue

    for i,j in move:
        nx=posx+i;ny=posy+j
        if H-1>=nx>=0 and W-1>=ny>=0 and A[nx][ny]!="#" and (nx,ny) not in start:
            start.add((nx,ny))
            heapq.heappush(que,(count+1,nx,ny))


ans=float("inf")
while start:
    x,y=start.pop()
    test=1+min((abs(x-0)-1)//K+1,(abs(H-1-x)-1)//K+1,(abs(y-0)-1)//K+1,(abs(W-1-y)-1)//K+1)
    ans=min(ans,test)

if s[0]==0 or s[0]==H-1 or s[1]==0 or s[1]==W-1:
    ans=0
print(ans)


Fixed submission:
from collections import deque

H,W,K=map(int,input().split())
A=["" for i in range(H)]
for i in range(H):
    A[i]=input()

for i in range(H):
    for j in range(W):
        if A[i][j]=="S":
            s=(i,j)

move=[(0,1),(1,0),(0,-1),(-1,0)]
start=set([s])
que=deque([(0,s[0],s[1])])
while que:
    count,posx,posy=que.popleft()
    if count==K:
        continue

    for i,j in move:
        nx=posx+i;ny=posy+j
        if H-1>=nx>=0 and W-1>=ny>=0 and A[nx][ny]!="#" and (nx,ny) not in start:
            start.add((nx,ny))
            que.append((count+1,nx,ny))


ans=float("inf")
for x,y in start:
    test=1+min((abs(x-0)-1)//K+1,(abs(H-1-x)-1)//K+1,(abs(y-0)-1)//K+1,(abs(W-1-y)-1)//K+1)
    ans=min(ans,test)

if s[0]==0 or s[0]==H-1 or s[1]==0 or s[1]==W-1:
    ans=0
print(ans)