Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import re
import numpy as np
n=int(input())
a=list(map(int,input().split()))

neye=np.eye(n)
neye_roll=np.roll(np.eye(n),1)
neye_roll[0][0]=0
neye_roll[n-1][0]=1
x=neye+neye_roll
#print(x)

avector=np.array(a)
avector=2*np.reshape(avector, (1,n)).T
#print(avector)
x_ans=np.linalg.solve(x, avector)
#print(x_ans)
ans=[]
for i in range(n):
    ans.append(int(x_ans[i][0]))
print(re.sub("[\[\]\,]","",str(ans)))

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

x=[]
s=sum(a)
x.append(s-2*sum(a[1::2]))
for i in range(1,n-1):
    x.append(2*a[i-1]-x[i-1])
x.append(2*a[n-1]-x[0])
print(*x)

Buggy python submission (verdict: Runtime Error):
import numpy as np

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

a = np.eye(N, k=0) + np.eye(N, k=1) + np.eye(N, k=1-N)

a_matrix = np.array(a)
b_matrix = np.array(A)

x = np.linalg.solve(a_matrix,b_matrix)

x = x * 2

for i in range(N):
    print(int(x[i]),end="")
    if(i != N-1):
        print(" ",end="")
print()


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

x=[]
s=sum(a)
x.append(s-2*sum(a[1::2]))
for i in range(1,n-1):
    x.append(2*a[i-1]-x[i-1])
x.append(2*a[n-1]-x[0])
print(*x)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

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

a = []
for i in range(N):
    ai = []
    for j in range(N):
        k = i+1 if i+1 < N else 0
        if(j == i or j == k):
            ai.append(1)
        else:
            ai.append(0)
    a.append(ai)

a_matrix = np.array(a)
b_matrix = np.array(A)

x = np.linalg.solve(a_matrix,b_matrix)

x = x * 2

for i in range(N):
    print(int(x[i]),end="")
    if(i != N-1):
        print(" ",end="")
print()


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

x=[]
s=sum(a)
x.append(s-2*sum(a[1::2]))
for i in range(1,n-1):
    x.append(2*a[i-1]-x[i-1])
x.append(2*a[n-1]-x[0])
print(*x)
Buggy python submission (verdict: Runtime Error):
import math

MOD = 1000000000 + 7

n = list(map(int,input().split()))
N = n[0]
K = n[1]

for i in range(1,K+1):
    blue = (math.factorial(K-1)/(math.factorial(K-i) * math.factorial(i-1))) % MOD
    red = (math.factorial(N-K+1)/(math.factorial(N-K-i+1) * math.factorial(i))) % MOD
    print((int)((red * blue) % MOD))

Fixed submission:
n,k=map(int,input().split())
ans=0
MOD=(10**9)+7

fact_ans=[1 for _ in range(n+1)]
for i in range(1,n+1):
    fact_ans[i]=fact_ans[i-1]*i

def fact(n):
    if(n<0):
        return 1
    else:
        return fact_ans[n]

for i in range(1,k+1):
    blue=fact(k-1)//(fact(k-i)*fact(i-1))
    red=( fact(n-k+1)//( fact(i)*fact(n-k+1-i))  )
    print((blue*red)%MOD)

Buggy python submission (verdict: Runtime Error):
import math

MOD = 1000000000 + 7

n = list(map(int,input().split()))
N = n[0]
K = n[1]

for i in range(1,K+1):
    blue = math.factorial(K-1)/(math.factorial(K-i) * math.factorial(i-1)) % MOD
    red = math.factorial(N-K+1)/(math.factorial(N-K-i+1) * math.factorial(i)) % MOD
    print((int)((red * blue) % MOD))

Fixed submission:
n,k=map(int,input().split())
ans=0
MOD=(10**9)+7

fact_ans=[1 for _ in range(n+1)]
for i in range(1,n+1):
    fact_ans[i]=fact_ans[i-1]*i

def fact(n):
    if(n<0):
        return 1
    else:
        return fact_ans[n]

for i in range(1,k+1):
    blue=fact(k-1)//(fact(k-i)*fact(i-1))
    red=( fact(n-k+1)//( fact(i)*fact(n-k+1-i))  )
    print((blue*red)%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import re
s=input()
ans=0

re_abc=re.compile(r'ABC')
while(True):

    abc_num=len(re.findall(re_abc,s))
    if(abc_num==0):
        break
    else:
        ans+=abc_num
        s=re.sub(re_abc,'BCA',s)
#    print(s)

print(ans)

Fixed submission:
import re
s=input()
ans=0

s=re.sub('BC', 'D', s)

re_ad=re.compile(r'[AD]+')
ad=re.findall(re_ad,s)
#print(s)
#print(ad)
for adi in ad:
    adi_a=0
    for adij in adi:
        if(adij=='A'):
            adi_a+=1
        else:
            ans+=adi_a

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=0
for i in range(2**n):
	bit_i=bin(i)[2:].zfill(n)
	vi=0
	ci=0
	for j in range(len(bit_i)):
		if(bit_i[j]=='1'):
			vi+=v[j]
			ci+=c[j]
	if(ans < vi-ci):
		ans=vi-ci
print(ans)

Fixed submission:
n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
diff=[v[i]-c[i] for i in range(n) if v[i]-c[i] > 0]
diff.append(0)
print(sum(diff))
Buggy python submission (verdict: Runtime Error):
a=''.join(list(sorted(list(map(int,input().split())))))
if(a=='1479'):
	print('YES')
else:
	print('NO')




Fixed submission:
a=''.join(list(sorted(list(input().split()))))
if(a=='1479'):
	print('YES')
else:
	print('NO')
Buggy python submission (verdict: Runtime Error):
N = int(input())
h = list(map(int,input().split()))

mincost = [-1] * N

def calcMinCost(n):
#    print("calcMinCost(" + str(n) + ")")
#    print(mincost)
    if(n == 0):
        mincost[0] = 0
        return 0
    elif(n == 1):
        mincost[1] = abs(h[1] - h[0])
        return abs(h[1] - h[0])
    elif(mincost[n-1] != -1 and mincost[n-2] != -1):
        a = mincost[n-1] + abs(h[n-1] - h[n])
        b = mincost[n-2] + abs(h[n-2] - h[n])
        mincost[n] = a if a < b else b
        return mincost[n]
    elif(mincost[n-1] != -1):
        a = mincost[n-1] + abs(h[n-1] - h[n])
        b = calcMinCost(n-2) + abs(h[n-2] - h[n])
        mincost[n] = a if a < b else b
        return mincost[n]
    elif(mincost[n-2] != -1):
        a = calcMinCost(n-1) + abs(h[n-1] - h[n])
        b = mincost[n-2] + abs(h[n-2] - h[n])
        mincost[n] = a if a < b else b
        return mincost[n]
    else:
        a = calcMinCost(n-1) + abs(h[n-1] - h[n])
        b = calcMinCost(n-2) + abs(h[n-2] - h[n])
        mincost[n] = a if a < b else b
        return mincost[n]


print(calcMinCost(N-1))


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

mincost = [-1] * N
mincost[0] = 0
mincost[1] = abs(h[1] - h[0])

for i in range(2,N):
    a = mincost[i-2] + abs(h[i] - h[i-2])
    b = mincost[i-1] + abs(h[i] - h[i-1])
    mincost[i] = a if a < b else b

print(mincost[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
a,b,c=map(int,input().split())
ans=0
poison=False
while(True):
    if(poison):
        if(b>0):
            b-=1
            ans+=1
        elif(a>0):
            a-=1
        else:
            break
        poison=False
    else:
        if(c>0):
            c-=1
            ans+=1
            poison=True
        elif(b>0):
            b-=1
            ans+=1
        elif(a>0):
            a-=1
        else:
            break
print(ans)

Fixed submission:
a,b,c=map(int,input().split())
if(c<=a+b):
	print(c+b)
else:
	print((a+b)+b+1)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()

ans=0

for i in range(len(s)):
    if(s[i]=='W'):
        ans+=list(s[:i]).count('B')
print(ans)

Fixed submission:
s=input()

ans=0
b_count=0
for i in range(len(s)):
    if(s[i]=='W'):
        ans+=b_count
    else:
        b_count+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=input()

ans=0

while(True):

    if(s.find('BW')== -1):
        break

    ind=-1
    while(True):
        ind=s.find('BW',ind+1)
        if(ind==-1):
            break
        else:
            ans+=1

    s=s.replace('BW', 'WB')
print(ans)

Fixed submission:
s=input()

ans=0
b_count=0
for i in range(len(s)):
    if(s[i]=='W'):
        ans+=b_count
    else:
        b_count+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
n,x=map(int,input().split())
s="P"
for _ in range(n):
    s='B'+s+'P'+s+'B'
print(s[-1*x:].count('P'))

Fixed submission:
n,x=map(int,input().split())


b=[1]
p=[1]
for i in range(n):
    b.append(2*b[-1]+3)
    p.append(2*p[-1]+1)

def f(N,X):
    if N==0:
        return 0 if X<=0 else 1
    elif X==1:
        return 0
    elif 1<X and X<=b[N-1]+1:
        return f(N-1,X-1)
    elif X==b[N-1]+2:
        return p[N-1]+1
    else:
        return p[N-1]+1+f(N-1,X-2-b[N-1])

print(f(n,x))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
for i in range((m//n)+1,0,-1):
    if(m%i==0 and m//i>=n):
        print(i)
        break

Fixed submission:
n,m=map(int,input().split())
i=1
x=[]
while(i*i<=m):
    if(m%i==0):
        x.append(i)
        x.append(m//i)
    i+=1
x.sort()
for xi in x:
    if(xi>=n):
        print(m//xi)
        break
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))

ans=[]
for i in range(h):
    for j in range(w):
        if(j==w-1 and i!=h-1 and a[i][j]%2!=0):
            a[i][j]-=1
            a[i+1][j]+=1
            ans.append([i,j,i+1,j])
        elif(a[i][j]%2!=0):
            a[i][j]-=1
            a[i][j+1]+=1
            ans.append([i,j,i,j+1])

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


Fixed submission:
h,w=map(int,input().split())
a=[]
used=[[False for _ in range(w)] for _ in range(h)]
ans=[]
for i in range(h):
    ai=list(map(int,input().split()))
    for j in range(w):
        if(ai[j]%2!=0):
            if(j<w-1 and ai[j]>0 and ai[j]%2!=0 and not used[i][j]):
                used[i][j]=True
                ai[j]-=1
                ai[j+1]+=1
                ans.append([i+1,j+1,i+1,j+2])
    a.append(ai)

for i in range(h):
    if(i<h-1 and a[i][w-1]>0 and a[i][w-1]%2!=0 and not used[i][w-1]):
        used[i][w-1]=True
        a[i][w-1]-=1
        a[i+1][w-1]+=1
        ans.append([i+1,w,i+2,w])

print(len(ans))
for i in range(len(ans)):
    print(*ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
b=[a[i]-(i+1) for i in range(n)]
ans=9999999999999999
for bi in set(b):
    ans=min(ans,sum([abs(b[j]-bi) for j in range(n)]))
print(ans)

Fixed submission:
import statistics
n=int(input())
a=list(map(int,input().split()))
b=[a[i]-(i+1) for i in range(n)]
b_median=statistics.median(b)
ans=int(sum([abs(b[i]-b_median) for i in range(n)]))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
b=[a[i]-(i+1) for i in range(n)]
ans=9999999999999999
min_b=min(b)
max_b=max(b)
for i in range(min_b,max_b+1):
    ans=min(ans,sum([abs(b[j]-i) for j in range(n)]))
print(ans)

Fixed submission:
import statistics
n=int(input())
a=list(map(int,input().split()))
b=[a[i]-(i+1) for i in range(n)]
b_median=statistics.median(b)
ans=int(sum([abs(b[i]-b_median) for i in range(n)]))
print(ans)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
h=[]
for i in range(n):
    h.append(int(input()))
h.sort()

ans=9999999999999
for i in range(n-k+1):
    ans=min(ans,h[i+k-1]-h[i])
print(ans)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
print(-(-(n-1)//(k-1)))
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input())
if(a+b%2==0):
    print('Yay!')
elif(a < 9 and b < 9):
    print('Yay!')
else:
    print(':(')

Fixed submission:
a,b=map(int,input().split())
if(a+b%2==0):
    print('Yay!')
elif(a < 9 and b < 9):
    print('Yay!')
else:
    print(':(')
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))

#累積和
ans=0
acum=[]
acumi=0
for i in range(n):
    acumi+=a[i]
    acum.append(acumi)
ans+=acum.count(0)
#print(a)
#print(acum)
i_ans=0
for i in range(n):
    i_ans+=a[i]
    ans+=acum[i+1:].count(i_ans)
#    print(ans,i_ans,acum[i+1:])
print(ans)


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

#累積和
ans=0
acum={}
acumi=0
for i in range(n):
    acumi+=a[i]
    acum[acumi]=acum.get(acumi, 0)+1

for k,v in acum.items():
    if(k==0):
        ans+=v*(1+v)//2
    else:
        ans+=(v-1)*v//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))

#累積和
ans=0
for i in range(n):
    acum=0
    for j in range(i,n):
        acum+=a[j]
        if(acum==0):
            ans+=1
print(ans)


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

#累積和
ans=0
acum={}
acumi=0
for i in range(n):
    acumi+=a[i]
    acum[acumi]=acum.get(acumi, 0)+1

for k,v in acum.items():
    if(k==0):
        ans+=v*(1+v)//2
    else:
        ans+=(v-1)*v//2
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)

def mid(a):
    if(a%2!=0):
        return (a+1)//2
    else:
        return a//2
ai=a[0]
temp=list(map(lambda x:abs(x-mid(ai)),a[1:]))
bi=a[temp.index(min(temp))+1]
print(str(ai)+" "+str(ans[bi]))

Fixed submission:
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)

def mid(a):
    if(a%2!=0):
        return (a+1)//2
    else:
        return a//2

ai=a[0]
temp=list(map(lambda x:abs(x-mid(ai)),a[1:]))
bi=a[temp.index(min(temp))+1]
print(str(ai)+" "+str(bi))

Buggy python submission (verdict: Time Limit Exceeded):
import math
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)
maxconb=0
ans=[0,0]

def comb(a,b):
    return math.factorial(a)//(math.factorial(a-b) * math.factorial(b))

def mid(a):
    if(a%2!=0):
        return (a+1)//2
    else:
        return a//2
#print(a)
for i in range(n-1):
    ai=a[i]
    temp=list(map(lambda x:abs(x-mid(ai)),a[i+1:]))
#    print(temp)
    bi=a[temp.index(min(temp))+i+1]
#    print(str(ai)+":"+str(bi))
    c=comb(ai,bi)
    if(maxconb<c):
        maxconb=c
        ans=[ai,bi]
print(str(ans[0])+" "+str(ans[1]))

Fixed submission:
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)

def mid(a):
    if(a%2!=0):
        return (a+1)//2
    else:
        return a//2

ai=a[0]
temp=list(map(lambda x:abs(x-mid(ai)),a[1:]))
bi=a[temp.index(min(temp))+1]
print(str(ai)+" "+str(bi))

Buggy python submission (verdict: Time Limit Exceeded):
import math
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)
maxcomb=0
ans=[0,0]

def combination(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

for i in range(1):
    for j in range(i+1,n):
        comb=combination(a[i], a[j])
        if(maxcomb < comb):
            maxcomb = comb
            ans=[a[i],a[j]]
print(str(ans[0])+" "+str(ans[1]))

Fixed submission:
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)

def mid(a):
    if(a%2!=0):
        return (a+1)//2
    else:
        return a//2

ai=a[0]
temp=list(map(lambda x:abs(x-mid(ai)),a[1:]))
bi=a[temp.index(min(temp))+1]
print(str(ai)+" "+str(bi))

Buggy python submission (verdict: Time Limit Exceeded):
import math
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)
maxcomb=0
ans=[0,0]

def combination(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

for i in range(n-1):
    for j in range(i+1,n):
        comb=combination(a[i], a[j])
        if(maxcomb < comb):
            maxcomb = comb
            ans=[a[i],a[j]]
print(str(ans[0])+" "+str(ans[1]))

Fixed submission:
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)

def mid(a):
    if(a%2!=0):
        return (a+1)//2
    else:
        return a//2

ai=a[0]
temp=list(map(lambda x:abs(x-mid(ai)),a[1:]))
bi=a[temp.index(min(temp))+1]
print(str(ai)+" "+str(bi))
Buggy python submission (verdict: Time Limit Exceeded):
a,b,k=map(int,input().split())
num=[i for i in range(a,b+1)]
ans=[]
ans.extend(num[:k])
ans.extend(num[-k:])
ans=sorted(list(set(ans)))
for ansi in ans:
    print(ansi)

Fixed submission:
a,b,k=map(int,input().split())
ans=[i for i in range(a,min(b,a+k))]
ans.extend([i for i in range(max(a,b-k+1),b+1)])
ans=sorted(list(set(ans)))
for ansi in ans:
    print(ansi)
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=list(map(int,input().split()))
if('Y' in s):
	print("Four")
else:
	print("Three")

Fixed submission:
n=int(input())
s=list(input().split())
if('Y' in s):
	print("Four")
else:
	print("Three")
Buggy python submission (verdict: Time Limit Exceeded):
h,w,d=map(int,input().split())
a=[]
box=[[] for i in range(h*w+1)]
wi=0
for i in range(h):
    ai=list(map(int,input().split()))
    for j in range(w):
        box[ai[j]]=[i,j]

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    ansi=0
    for j in range(l,r,d):
        ansi+=abs(box[j][0]-box[j+d][0])+abs(box[j][1]-box[j+d][1])
    print(ansi)


Fixed submission:
h,w,d=map(int,input().split())
a=[]
box=[[] for i in range(h*w+1)]
wi=0
for i in range(h):
    ai=list(map(int,input().split()))
    for j in range(w):
        box[ai[j]]=[i,j]

p=[0]
for i in range(1,h*w+1):
    if(i-d>0):
        p.append(p[i-d]+abs(box[i][0]-box[i-d][0])+abs(box[i][1]-box[i-d][1]))
    else:
        p.append(0)

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(p[r]-p[l])
Buggy python submission (verdict: Runtime Error):
import sys
n=int(input())

def flush():
    sys.stdout.write("\033[2K\033[G")
    sys.stdout.flush()

print(0)
s=input()
if(s=='Vacant'):
    sys.exit()
flush()
pre_i=0
i=(n-1)//2
while(True):
    print(i)
    si=input()
    if(si=='Vacant'):
        break
    temp=i
    if(s==si):
        i=i+(i-pre_i)//2
    else:
        i=i-(i-pre_i)//2
    s=si
    pre_i=temp




Fixed submission:
import sys
n=int(input())

print(0)
sexlow=input()
if(sexlow=='Vacant'):
    sys.exit()

print(n-1)
sexhigh=input()
if(sexhigh=='Vacant'):
    sys.exit()

low=0
high=n-1
piv=0
while(True):
    piv=(low+high)//2

    print(piv)
    sexn=input()
    if(sexn=='Vacant'):
        break
    elif(( (piv-low)%2==0 and sexlow!=sexn) or ( (piv-low)%2!=0 and sexlow==sexn)):
        high=piv
        sexhigh=sexn
    elif(( (high-piv)%2==0 and sexhigh!=sexn) or ( (high-piv)%2!=0 and sexhigh==sexn)):
        low=piv
        sexlow=sexn
Buggy python submission (verdict: Runtime Error):
import math
n=int(input())
k=int(input())

b=2**n
ans=math.inf
for i in range(b):
    bit_b=bin(i)[2:].zfill(n)
    ans_i=1
    for j in range(len(bit_b)):
        if(bit_b[j]=='0'):
            ans_i*=2
        elif(bit_b[j]=='1'):
            ans_i+=k

    if(ans>ans_i):
        ans=ans_i

print(ans)

Fixed submission:
n=int(input())
k=int(input())

b=2**n
ans=999999999999999999
for i in range(b):
    bit_b=bin(i)[2:].zfill(n)
    ans_i=1
    for j in range(len(bit_b)):
        if(bit_b[j]=='0'):
            ans_i*=2
        elif(bit_b[j]=='1'):
            ans_i+=k

    if(ans>ans_i):
        ans=ans_i

print(ans)
Buggy python submission (verdict: Runtime Error):
x,t=map(int.input().split())
print(x-t)

Fixed submission:
x,t=map(int,input().split())
print(x-t if x >= t else 0)

Buggy python submission (verdict: Runtime Error):
x,t=map(int.input())
print(x-t)

Fixed submission:
x,t=map(int,input().split())
print(x-t if x >= t else 0)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

def dec(a):
    return a-1

def inc(a):
    return a+1

a = list(map(int,input().split()))
b = list(map(dec,a))
c = list(map(inc,a))

count = a+b+c

set_c = list(set(count))

c = {}
for i in range(len(set_c)):
    c[set_c[i]] = count.count(set_c[i])

print(max(c.values()))

Fixed submission:
N = int(input())

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

x = {}

for i in range(N):

    ai = a[i]

    temp = x.get(ai-1, 0)
    temp += 1
    x[ai-1] = temp

    temp = x.get(ai, 0)
    temp += 1
    x[ai] = temp

    temp = x.get(ai+1, 0)
    temp += 1
    x[ai+1] = temp

X = max(x.values())
print(X)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
s=[]
for i in range(n):
    a,b=map(int,input().split())
    s.extend([a for _ in range(b)])
s.sort()
print(s[k-1])

Fixed submission:
import bisect
n,k=map(int,input().split())
s=[0 for _ in range((10**5)+1)]
maxa=0
for i in range(n):
    a,b=map(int,input().split())
    s[a]+=b
    maxa=max(maxa,a)
s=s[:maxa]
#print(s)
for i in range(1,len(s)):
    s[i]+=s[i-1]
#print(s)
print(bisect.bisect_left(s, k))
Buggy python submission (verdict: Time Limit Exceeded):
import copy

n = int(input())
a = list(map(int,input().split()))
b = [0]

for i in range(len(a)):
    b.append(b[i] + a[i])

del b[0]

c = copy.copy(b)

first_minus = 0
first_plus = 0

for i in range(len(b)):
    if(i%2 == 0):
        if (b[i] >= 0):
            diff =  abs(b[i]) + 1
            first_minus = first_minus +  diff
            b = list(map(lambda x: x - diff, b))

        if (c[i] <= 0):
            diff =  abs(c[i]) + 1
            first_plus = first_plus +  diff
            c = list(map(lambda x: x + diff, c))
    else:
        if (b[i] <= 0):
            diff =  abs(b[i]) + 1
            first_minus = first_minus +  diff
            b = list(map(lambda x: x + diff, b))

        if (c[i] >= 0):
            diff =  abs(c[i]) + 1
            first_plus = first_plus +  diff
            c = list(map(lambda x: x - diff, c))

print(min(first_minus,first_plus))

Fixed submission:
import copy

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

ans_a = 0
for i in range(len(a)):
    sum += a[i]
    if(i%2 == 0):
        if(sum >= 0):
            ans_a += sum + 1
            sum = -1
    else:
        if(sum <= 0):
            ans_a += 1 - sum
            sum = 1

sum = 0
ans_b = 0
for i in range(len(a)):
    sum += a[i]
    if(i%2 == 0):
        if(sum <= 0):
            ans_b += 1 - sum
            sum = 1
    else:
        if(sum >= 0):
            ans_b += sum + 1
            sum = -1

print(min(ans_a,ans_b))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
ai_sum=0
for i in range(n):
    ai_sum+=a[i]
    clear=True
    scale=ai_sum
    for j in range(i+1,n):
        if(2*scale>=a[j]):
            scale+=a[j]
        else:
#            print(i,j,scale)
            i=j
            clear=False
            break

    if(clear):
        ans=n-i
        break

print(ans)


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=n
sum_former=sum(a)
for i in range(n-1,-1,-1):
    sum_former-=a[i]
    if(2*sum_former < a[i]):
        ans=n-i
        break

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
ai_sum=0
for i in range(n):
	ai_sum+=a[i]
	clear=True
	scale=ai_sum
	for j in range(i+1,n):
		if(2*scale>=a[j]):
			scale+=a[j]
		else:
#			print(i,j,scale)
			clear=False
			break
	
	if(clear):
		ans=n-i
		break

print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=n
sum_former=sum(a)
for i in range(n-1,-1,-1):
    sum_former-=a[i]
    if(2*sum_former < a[i]):
        ans=n-i
        break

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
for i in range(n):
	a_bkup=a
	ai=a[i]
	clear=True
	scale=0
	for j in range(n):
		if(j<=i):
			scale+=a[j]
		elif(2*scale>=a[j]):
			scale+=a[j]
		else:
#			print(i,j,scale)
			clear=False
			break
	
	if(clear):
		ans=n-i
		break

print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=n
sum_former=sum(a)
for i in range(n-1,-1,-1):
    sum_former-=a[i]
    if(2*sum_former < a[i]):
        ans=n-i
        break

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)
start_i=0
end=False
#print(a)
while(not end):
    max_a=a[start_i]
    for i in range(start_i,n):
        if(max_a>2*sum(a[i:])):
            if(start_i==i-1):
                end=True
            else:
                start_i=i-1
            break
        if(i==n-1):
            start_i=i
            end=True
#    print(start_i)
print(start_i+1)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=n
sum_former=sum(a)
for i in range(n-1,-1,-1):
    sum_former-=a[i]
    if(2*sum_former < a[i]):
        ans=n-i
        break

print(ans)