Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,T=[int(s) for s in input().split()]
food=[[int(s) for s in input().split()] for i in range(N)]
food.sort()

#i番目までの料理でt秒以内に食べきるときのDP
DP=[[0 for t in range(T)] for i in range(N)]
for i in range(N):
  time,point=food[i]
  for t in range(min([T,time])):
    DP[i][t]=DP[i-1][t]
  for t in range(time,T):
    DP[i][t]=max([DP[i-1][t] , DP[i-1][t-time]+point])

#i番目の料理を最後に注文することを考える
ls=[DP[i-1][T-1]+food[i][1] for i in range(1,N)]
ls.append(food[0][1])
print(max(ls))  

Fixed submission:
N,T=[int(s) for s in input().split()]
food=[[int(s) for s in input().split()] for i in range(N)]
food.sort()

#i番目までの料理でt秒以内に食べきるときのDP
DP=[[0 for t in range(T)] for i in range(N)]
for i in range(N):
  time,point=food[i]
  for t in range(min([T,time])):
    DP[i][t]=DP[i-1][t]
  for t in range(time,T):
    DP[i][t]=max([DP[i-1][t] , DP[i-1][t-time]+point])

#i番目の料理を最後に注文することを考える
ls=[DP[i-1][T-1]+food[i][1] for i in range(1,N)]
ls.append(food[0][1])
print(max(ls))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A1=[int(s) for s in input().split()]
B1=[int(s) for s in input().split()]
A2=[(A1[i],i) for i in range(N)]
B2=[(B1[i],i) for i in range(N)]
A=sorted(A2)
B=sorted(B2)
#print(A)
#print(B)
for i in range(N):
  if B[i][0]<A[i][0]:
    print("No")
    break
else:
  for i in range(N-1):
    if B[i][0]>=A[i+1][0]:
      print("Yes")
      break
  else:
    C=[e[1] for e in A]
    a=C[0]
  #  print(a)
    k=B[0][1]
    for i in range(N-2):
      k=B[C.index(k)][1]
   #   print(k)
      if k==a :
        print("Yes")
        break
    else:
      print("No")
        


Fixed submission:
N=int(input())
A1=[int(s) for s in input().split()]
B1=[int(s) for s in input().split()]
A2=[(A1[i],i) for i in range(N)]
B2=[(B1[i],i) for i in range(N)]
A=sorted(A2)
B=sorted(B2)
#print(A)
#print(B)
for i in range(N):
  if B[i][0]<A[i][0]:
    print("No")
    break
else:
  for i in range(N-1):
    if B[i][0]>=A[i+1][0]:
      print("Yes")
      break
  else:
    C=[(A[i][1],B[i][1]) for i in range(N)]
    C.sort()
#    print(C)
    k=0
    for i in range(N-1):
      k=C[k][1]
      if k==0:
        print("Yes")
        break
    else:
      print("No")
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N=int(input())
ls=[int(s) for s in input().split()]
ls.sort()
ans=0
for i in range(1,N-1):
  for j in range(i+1,N):
    k = bisect.bisect_right(ls[:i],ls[j]-ls[i])
    ans+=i-k
print(ans)

        
        
        
  

Fixed submission:
import bisect
N=int(input())
ls=[int(s) for s in input().split()]
ls.sort()
ans=0
for i in range(1,N-1):
  for j in range(i+1,N):
    k = bisect.bisect_right(ls[:i],ls[j]-ls[i])
    ans+=i-k
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ls=[int(s) for s in input().split()]
ls.sort()
ls.reverse()
ls2=[ls[0],ls[1]]
def plus(lst,num):
  val=0
  n=len(lst)
  for i in range(n):
    for k in range(1,n+1):
      if i+k>=n:
        val+=k-1
        break
      if lst[i]-lst[i+k]>=num:
        val+=k-1
        break
  return val
ans=0
for j in range(2,N):
  ans+=plus(ls2,ls[j])
  ls2.append(ls[j])
print(ans)

Fixed submission:
import bisect
N=int(input())
ls=[int(s) for s in input().split()]
ls.sort()
ans=0
for i in range(1,N-1):
  for j in range(i+1,N):
    k = bisect.bisect_right(ls[:i],ls[j]-ls[i])
    ans+=i-k
print(ans)
Buggy python submission (verdict: Runtime Error):
x=int(input())
y=x//2
z=x-y
print(z/y)

Fixed submission:
x=int(input())
y=x//2
z=x-y
print(z/x)

Buggy python submission (verdict: Runtime Error):
x=int(input())
y=x//2
z=x-1
print(z/y)

Fixed submission:
x=int(input())
y=x//2
z=x-y
print(z/x)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
ls2=[0]
ls.append(-1)
index=0
for i in range(M):
  x=ls2[-1]
  if x<ls[index]:
    ls2.append(ls[index])
    index+=1
  ls2[-1]//=2
  ls2.sort()
#  print(ls2,index,ls)
print(sum(ls2)+sum(ls[index:])+1)


Fixed submission:
import math
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
x=ls[0]
L=int(math.log2(x))
#2**L より大きいものをわける
def cut(lst,exp):
    for ii in range(len(lst)):
        if ii+1==len(lst):
            break
        if lst[ii+1]<exp:
           break
    return ii
m=M #残り回数
b=-1
ls3=[]
while True:
    if m==0:
        break
    a=b+1
    b=cut(ls,2**L)
    ls2=ls[a:b+1]
    ls3=ls3+ls2
    ls3.sort(reverse=True)
    for j in range(len(ls3)):
        ls3[j]=ls3[j]//2
        m-=1
        if m==0:
            break
    L-=1
#    print(ls3,m,b)
#print(ls3,ls[b+1:])
s=sum(ls3)+sum(ls[b+1:])
print(s)

Buggy python submission (verdict: Time Limit Exceeded):
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
#print(ls)
for i in range(M):
  x=max(ls)
  y=x//2
  ls[ls.index(x)]=y
print(sum(ls))


Fixed submission:
import math
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
x=ls[0]
L=int(math.log2(x))
#2**L より大きいものをわける
def cut(lst,exp):
    for ii in range(len(lst)):
        if ii+1==len(lst):
            break
        if lst[ii+1]<exp:
           break
    return ii
m=M #残り回数
b=-1
ls3=[]
while True:
    if m==0:
        break
    a=b+1
    b=cut(ls,2**L)
    ls2=ls[a:b+1]
    ls3=ls3+ls2
    ls3.sort(reverse=True)
    for j in range(len(ls3)):
        ls3[j]=ls3[j]//2
        m-=1
        if m==0:
            break
    L-=1
#    print(ls3,m,b)
#print(ls3,ls[b+1:])
s=sum(ls3)+sum(ls[b+1:])
print(s)

Buggy python submission (verdict: Time Limit Exceeded):
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
#print(ls)
for i in range(M):
  x=ls[0]>>1
  for j in range(N-1):
    if ls[j+1]>x:
      ls[j]=ls[j+1]
    else:
      ls[j]=x
      break
#    print(ls,j,x)
  else:
    ls[N-1]=x
#  print(ls)
print(sum(ls))


Fixed submission:
import math
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
x=ls[0]
L=int(math.log2(x))
#2**L より大きいものをわける
def cut(lst,exp):
    for ii in range(len(lst)):
        if ii+1==len(lst):
            break
        if lst[ii+1]<exp:
           break
    return ii
m=M #残り回数
b=-1
ls3=[]
while True:
    if m==0:
        break
    a=b+1
    b=cut(ls,2**L)
    ls2=ls[a:b+1]
    ls3=ls3+ls2
    ls3.sort(reverse=True)
    for j in range(len(ls3)):
        ls3[j]=ls3[j]//2
        m-=1
        if m==0:
            break
    L-=1
#    print(ls3,m,b)
#print(ls3,ls[b+1:])
s=sum(ls3)+sum(ls[b+1:])
print(s)
Buggy python submission (verdict: Runtime Error):
A,B= [int(s) for s in input().split()]
x=1
if B=1:
  print(0)
else:
  for i in range(100):
    x+=A-1
    if x>=B:
      break
  print(i+1)

Fixed submission:
A,B= [int(s) for s in input().split()]
i=0
while(True):
  if B<=1:
    break
  B-=A-1
  i+=1
print(i)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
lst=[]
for i in range(N):
  text=input()
  lst=lst+[sorted(text)]
lst=sorted(lst)      
count=0
i=0
while(i<N-1):
  j=1
  while(lst[i]==lst[i+j]):
    count=count+j
    j=j+1
    if (i+j >= N):
      break
  i=i+j
print(count)

  

Fixed submission:
N=int(input())
d={}
for i in range(N):
  text=''.join(sorted(input()))
  if text in d :
    d[text]+=1
  else:
    d[text]=1
count=0
for v in d.values() :
  count+=(v-1)*v/2
print(int(count))

Buggy python submission (verdict: Runtime Error):
N=int(input())
lst=[]
for i in range(N):
  text=input()
  lst=lst+[sorted(text)]
lst=sorted(lst)      
count=0
i=0
while(i<N):
  j=1
  while(lst[i]==lst[i+j]):
    count=count+j
    j=j+1
    if (i+j >= N):
      break
  i=i+j
print(count)

  

Fixed submission:
N=int(input())
d={}
for i in range(N):
  text=''.join(sorted(input()))
  if text in d :
    d[text]+=1
  else:
    d[text]=1
count=0
for v in d.values() :
  count+=(v-1)*v/2
print(int(count))
Buggy python submission (verdict: Time Limit Exceeded):
M=10**9+7
remain=[1,0,0,0,0,0,0,0,0,0,0,0,0]

#リストに入力（文字列）
text=input()
lst=list(text)
lst.reverse()


##漸化式を用意
ind=[1,-3,-4,-1,3,4]
def rec(ls,num,dig):
  val_ls=[0]*13
  if num!="?":
    for i in range(13):
      val_ls[i]=val_ls[i]+ls[(i-ind[dig]*int(num))%13]%M
  else:
    for i in range(13):
      for j in range(10):
        val_ls[i]=val_ls[i]+ls[(i-ind[dig]*j)%13]
        val_ls[i]=val_ls[i]%M
  return val_ls

##漸化式をremainに適用
for k in range(len(lst)):
  remain=rec(remain,lst[k],k%6)
  
print(remain[5])


Fixed submission:
M=10**9+7
#リストに入力（文字列）
text=input()
lst=list(text)
lst.reverse()
digit=len(lst)
six=[[0,0],[0,0],[0,0],[0,0],[0,0],[0,0]]
for i in range(digit):
  if(lst[i]=="?"):
    six[i%6][1]=six[i%6][1]+1
  else:
    six[i%6][0]=(six[i%6][0]+int(lst[i]))%13
rem=-(six[0][0]+10*six[1][0]+9*six[2][0]+12*six[3][0]+3*six[4][0]+4*six[5][0]-5)%13
######(?のいじったもの)+rem=0(mod13)
######(?*1+?*10+?*9+?*12+?*3+?*4)+rem=0
modulos=[1,0,0,0,0,0,0,0,0,0,0,0,0]
def mat1(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-1)%13]+ls[(i-2)%13]+ls[(i-3)%13]+ls[(i-4)%13]+ls[(i-5)%13]+ls[(i-6)%13]+ls[(i-7)%13]+ls[(i-8)%13]+ls[(i-9)%13])%M
  return val_ls
def mat10(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-10)%13]+ls[(i-20)%13]+ls[(i-30)%13]+ls[(i-40)%13]+ls[(i-50)%13]+ls[(i-60)%13]+ls[(i-70)%13]+ls[(i-80)%13]+ls[(i-90)%13])%M
  return val_ls
def mat100(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-9)%13]+ls[(i-18)%13]+ls[(i-27)%13]+ls[(i-36)%13]+ls[(i-45)%13]+ls[(i-54)%13]+ls[(i-63)%13]+ls[(i-72)%13]+ls[(i-81)%13])%M
  return val_ls
def mat1000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i+1)%13]+ls[(i+2)%13]+ls[(i+3)%13]+ls[(i+4)%13]+ls[(i+5)%13]+ls[(i+6)%13]+ls[(i+7)%13]+ls[(i+8)%13]+ls[(i+9)%13])%M
  return val_ls
def mat10000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-3)%13]+ls[(i-6)%13]+ls[(i-9)%13]+ls[(i-12)%13]+ls[(i-15)%13]+ls[(i-18)%13]+ls[(i-21)%13]+ls[(i-24)%13]+ls[(i-27)%13])%M
  return val_ls
def mat100000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-4)%13]+ls[(i-8)%13]+ls[(i-12)%13]+ls[(i-16)%13]+ls[(i-20)%13]+ls[(i-24)%13]+ls[(i-28)%13]+ls[(i-32)%13]+ls[(i-36)%13])%M
  return val_ls
for j in range(six[0][1]):
  modulos=mat1(modulos)
for j in range(six[1][1]):
  modulos=mat10(modulos)
for j in range(six[2][1]):
  modulos=mat100(modulos)
for j in range(six[3][1]):
  modulos=mat1000(modulos)
for j in range(six[4][1]):
  modulos=mat10000(modulos)
for j in range(six[5][1]):
  modulos=mat100000(modulos)
print(modulos[rem])
Buggy python submission (verdict: Runtime Error):
N,D = [int(s) for s in input().split()]
print(math.ceil(N/(2*D+1)))

Fixed submission:
import math

N,D = [int(s) for s in input().split()]
print(math.ceil(N/(2*D+1)))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ls=[]
for i in range(N):
  ls.append(int(input()))
for i in range(N):
  x=ls[0]
  ls.pop(0)
  print(max(ls))
  ls.append(x)

Fixed submission:
N=int(input())
maxi=0
smaxi=0
flag=0
ls=[]
x=0
for i in range(N):
  x=int(input())
  ls.append(x)
  if (maxi<x):
    smaxi=maxi
    maxi=x
  elif (maxi==x):
    smaxi=maxi
  elif (smaxi<x):
    smaxi=x
for i in range(N):
  if (ls[i]==maxi):
    print(smaxi)
  else:
    print(maxi)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
lst = [int(s) for s in input().split()]
ans=[0]*N
result=[]
def divls(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
for i in range(N):
  n=N-1-i
  x=lst[n]
  y=ans[n]
  if(x!=y):
    result.append(n+1)
    divisors=divls(n+1)
    for j in range(len(divisors)):
      ans[divisors[j]-1]=1-ans[divisors[j]-1]
result.sort()
print(len(result))
if (len(result)!=0):
  print(' '.join(map(str, result)))

Fixed submission:
N=int(input())
lst = [int(s) for s in input().split()]
ans=[0]*N
result=[]
def now(num):
  res=0
  k=1
  while(k*num<=N):
    res=res+ans[k*num-1]
    k=k+1
  return res%2
for i in range(N):
  n=N-i
  x=lst[n-1]
  y=now(n)
  if(x!=y):
    ans[n-1]=1
    result.append(n)
result.sort()
print(len(result))
if (len(result)!=0):
  print(' '.join(map(str, result)))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ls=[int(input()) for _ in range(N)]
color=[ls[-1]]
ans=1
for i in range(N-1):
  a=ls[-2-i]
  for j in range(ans):
    if a<color[j]:
      color[j]=a
      break
  else:
    color.append(a)
    ans+=1
print(ans)

Fixed submission:
import bisect
N=int(input())
ls=[int(input()) for _ in range(N)]
color=[ls[-1]]
ans=1
for i in range(N-1):
  a=ls[-2-i]
  k=bisect.bisect_right(color,a)
  if k==ans:
    color.append(a)
    ans+=1
  else:
    color[k]=a
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ls=[]
for i in range(N):
  x=int(input())
  ls.append(x)
result=[]
result.append([ls[0]])
for i in range(1,N):
  j=1
  while(j<=len(result)):
    if(ls[i]>result[-j][-1]):
      result[-j].append(ls[i])
      break
    j=j+1
  if(j>len(result)):
    result.append([ls[i]])
print(len(result))

Fixed submission:
import bisect
N=int(input())
ls=[int(input()) for _ in range(N)]
color=[ls[-1]]
ans=1
for i in range(N-1):
  a=ls[-2-i]
  k=bisect.bisect_right(color,a)
  if k==ans:
    color.append(a)
    ans+=1
  else:
    color[k]=a
print(ans)
Buggy python submission (verdict: Runtime Error):
N=input()
ls=[int(s) for s in input().split()]
ls.sort()
print(ls[N//2]-ls[N//2-1])

Fixed submission:
N=int(input())
ls=[int(s) for s in input().split()]
ls.sort()
print(ls[N//2]-ls[N//2-1])
Buggy python submission (verdict: Runtime Error):
N,X= [int(s) for s in input().split()]
lst = [int(s) for s in input().split()]
dist=0
count=0
while(1):
  dist=dist+lst[count]
  if(dist>X or count==N):
    break
  count=count+1
print(count+1)
  


Fixed submission:
N,X= [int(s) for s in input().split()]
lst = [int(s) for s in input().split()]
dist=0
count=0
while(count<N):
  dist=dist+lst[count]
  if(dist>X):
    break
  count=count+1
print(count+1)
Buggy python submission (verdict: Time Limit Exceeded):
H,W=[int(s) for s in input().split()]
lamp=[input() for _ in range(H)]
#Lを計算
L=[[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  if lamp[i][0]=="#" :  L[i][0]=0
  else: L[i][0]=1
  for j in range(1,W):
    if lamp[i][j]=="#" : L[i][j]=0
    else: L[i][j]=L[i][j-1]+1
#Rを計算
R=[[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  if lamp[i][W-1]=="#" :  R[i][W-1]=0
  else: R[i][W-1]=1
  for j in range(1,W):
    if lamp[i][W-1-j]=="#" : R[i][W-1-j]=0
    else: R[i][W-1-j]=R[i][W-j]+1
#Uを計算
U=[[0 for _ in range(W)] for _ in range(H)]
for j in range(W):
  if lamp[0][j]=="#" :  U[0][j]=0
  else: U[0][j]=1
  for i in range(1,H):
    if lamp[i][j]=="#" : U[i][j]=0
    else: U[i][j]=U[i-1][j]+1
#Dを計算
D=[[0 for _ in range(W)] for _ in range(H)]
for j in range(W):
  if lamp[H-1][j]=="#" :  D[H-1][j]=0
  else: D[H-1][j]=1
  for i in range(1,H):
    if lamp[H-1-i][j]=="#" : D[H-1-i][j]=0
    else: D[H-1-i][j]=D[H-i][j]+1
ls=[]
for i in range(H):
  for j in range(W):
    ls.append(L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(max(ls))

Fixed submission:
H,W=[int(s) for s in input().split()]
lamp=[input() for _ in range(H)]
#Lを計算
L=[[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  if lamp[i][0]=="#" :  L[i][0]=0
  else: L[i][0]=1
  for j in range(1,W):
    if lamp[i][j]=="#" : L[i][j]=0
    else: L[i][j]=L[i][j-1]+1
#Rを計算
R=[[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  if lamp[i][W-1]=="#" :  R[i][W-1]=0
  else: R[i][W-1]=1
  for j in range(1,W):
    if lamp[i][W-1-j]=="#" : R[i][W-1-j]=0
    else: R[i][W-1-j]=R[i][W-j]+1
#Uを計算
U=[[0 for _ in range(W)] for _ in range(H)]
for j in range(W):
  if lamp[0][j]=="#" :  U[0][j]=0
  else: U[0][j]=1
  for i in range(1,H):
    if lamp[i][j]=="#" : U[i][j]=0
    else: U[i][j]=U[i-1][j]+1
#Dを計算
D=[[0 for _ in range(W)] for _ in range(H)]
for j in range(W):
  if lamp[H-1][j]=="#" :  D[H-1][j]=0
  else: D[H-1][j]=1
  for i in range(1,H):
    if lamp[H-1-i][j]=="#" : D[H-1-i][j]=0
    else: D[H-1-i][j]=D[H-i][j]+1
ls=[]
for i in range(H):
  for j in range(W):
    ls.append(L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(max(ls))
Buggy python submission (verdict: Runtime Error):
a,b = [int(s) for s in input().split()]
if a>=13:
  print(b)
elif a<=6:
  print(b/2)
else:
  print 0

Fixed submission:
a,b = [int(s) for s in input().split()]
if a>=13:
  print(b)
elif a>=6:
  print(b//2)
else:
  print(0)
Buggy python submission (verdict: Runtime Error):
A,B=[int(s) for s in input().split()]
if A>B:
  print(2*A-1)
elif A=B:
  print(2*A)
else:
  print(2*B-1)

Fixed submission:
A,B=[int(s) for s in input().split()]
if A>B:
  print(2*A-1)
elif A==B:
  print(2*A)
else:
  print(2*B-1)
Buggy python submission (verdict: Runtime Error):
ls=[]
for i in range(5):
  ls.append(int(input()))
ls.sort()
if ls[4]-ls[0]>k:
  print(":(")
else:
  print("Yay!")

Fixed submission:
ls=[]
for i in range(5):
  ls.append(int(input()))
ls.sort()
if ls[4]-ls[0]>int(input()):
  print(":(")
else:
  print("Yay!")
Buggy python submission (verdict: Runtime Error):
X=input()
if X=="A":
  print("T")
elif X="T":
  print("A")
elif X="G":
  print("C")
else:
  print("G")

Fixed submission:
X=input()
if X=="A":
  print("T")
elif X=="T":
  print("A")
elif X=="G":
  print("C")
else:
  print("G")
Buggy python submission (verdict: Time Limit Exceeded):
N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst=lst+[[int(s) for s in input().split()]]
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)

Fixed submission:
N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst.append([int(s) for s in input().split()])
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)

Buggy python submission (verdict: Time Limit Exceeded):
N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst=lst+[[int(s) for s in input().split()]]
lst.sort()
n=0
cost=0
for i in range(N):
  n+=lst[i][1]
  cost+=lst[i][0]*lst[i][1]
  if(n>=M):
    break
if(n>M):
  cost-=lst[i][0]*(n-M)
print(cost)

Fixed submission:
N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst.append([int(s) for s in input().split()])
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)

Buggy python submission (verdict: Time Limit Exceeded):
N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  a,b = [int(s) for s in input().split()]
  lst=lst+[[a,b,a*b]]
lst.sort()
m=0
i=0
cost=0
while(m<M):
  m+=lst[i][1]
  cost+=lst[i][2]
  i+=1
if(m>M):
  cost-=lst[i-1][0]*(m-M)
print(cost)

Fixed submission:
N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst.append([int(s) for s in input().split()])
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)

Buggy python submission (verdict: Time Limit Exceeded):
N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst=lst+[[int(s) for s in input().split()]]
lst.sort()
n=0
i=0
cost=0
while(n<M):
  n+=lst[i][1]
  cost+=lst[i][0]*lst[i][1]
  i+=1
if(n>M):
  cost-=lst[i-1][0]*(n-M)
print(cost)

Fixed submission:
N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst.append([int(s) for s in input().split()])
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)
Buggy python submission (verdict: Runtime Error):
n=int(input())
x=0
for i in range(n):
  a,b=input().split()
  if b=="JPY":
    x+=int(input())
  else:
    x+=float(input())*380000
print(x)

Fixed submission:
n=int(input())
x=0
for i in range(n):
  a,b=input().split()
  if b=="JPY":
    x+=int(a)
  else:
    x+=float(a)*380000
print(x)
Buggy python submission (verdict: Runtime Error):
N,K=[int(s) for s in input().split()]
ls_p=[int(s) for s in input().split()]
ls_n=[]
X=0
for i in range(N):
  if ls_p[0]>=0 : break 
  else:
    X+=1
    ls_n.append(ls_p[0])
    ls_p.pop(0)
#ls_nにX個流れている
cand=[]
for i in range(min([X-1,K-2])):
  cand.append(-ls_n[-i-1]*2+ls_p[K-i-2])
  cand.append(-ls_n[-i-1]+ls_p[K-i-2]*2)
if N-X-1>=K-1:
  cand.append(ls_p[K-1])
if X>=K:
  cand.append(-ls_n[-K])
print(min(cand))
  


Fixed submission:
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
def length(i):
  if ls[i]>=0:
    return ls[K+i-1]
  elif ls[K+i-1]<=0:
    return -ls[i]
  else:
    return min([2*ls[K+i-1]-ls[i],ls[K+i-1]-2*ls[i]])
answer=[]
for i in range(N-K+1):
  answer.append(length(i))
  
print(min(answer))

Buggy python submission (verdict: Runtime Error):
N,K=[int(s) for s in input().split()]
ls_p=[int(s) for s in input().split()]
ls_n=[]
X=0
for i in range(N):
  if ls_p[0]>=0 : break 
  else:
    X+=1
    ls_n.append(ls_p[0])
    ls_p.pop(0)
print(ls_n)
print(ls_p)
#ls_nにX個流れている
cand=[]
for i in range(min([X-1,K-2])):
  cand.append(-ls_n[-i-1]*2+ls_p[K-i-2])
  cand.append(-ls_n[-i-1]+ls_p[K-i-2]*2)
if N-X-1>=K-1:
  cand.append(ls_p[K-1])
if X>=K:
  cand.append(-ls_n[-K])
print(min(cand))
  

Fixed submission:
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
def length(i):
  if ls[i]>=0:
    return ls[K+i-1]
  elif ls[K+i-1]<=0:
    return -ls[i]
  else:
    return min([2*ls[K+i-1]-ls[i],ls[K+i-1]-2*ls[i]])
answer=[]
for i in range(N-K+1):
  answer.append(length(i))
  
print(min(answer))
Buggy python submission (verdict: Runtime Error):
n=int(input())
if n==0:
  print('0')
else:
  ls=[]
  while(n!=0):
    ls.append(n%2)
    n=-1*(n-n%2)//2
ls.sort(reverse:True)
print(ls)
    
  
    

Fixed submission:
n=int(input())
if n==0:
  print('0')
else:
  ls=[]
  while(n!=0):
    ls.append(str(n%2))
    n=-1*(n-n%2)//2
  ls.reverse()
  oneLinerString="".join(ls)
  print(oneLinerString)
Buggy python submission (verdict: Runtime Error):
S=list(input())
x=S.pop(0)
if x!='A':
  print('WA')
else:
  for i in range(1,len(S)-1):
    if S[i]=='C':
      del S[i]
      if str.islower("".join(S)):
        print('AC')
        break
      else:
        print('WA')
  else:
    print('WA')

Fixed submission:
S=list(input())
x=S.pop(0)
if x!='A':
  print('WA')
else:
  for i in range(1,len(S)-1):
    if S[i]=='C':
      del S[i]
      if str.islower("".join(S)):
        print('AC')
        break
      else:
        print('WA')
        break
  else:
    print('WA')
Buggy python submission (verdict: Runtime Error):
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
def ceil(n,m):
  if n%m==0:
    return n//m
  else:
    return (n//m)+1
a=ls.index(1)
if K==N:
  print(1)
elif (K==N-1 and (a==0 or a==N-1)):
  print(1):
else:
  print(ceil(a,K-1)+ceil(N-a-1,K-1))




Fixed submission:
N,K=[int(s) for s in input().split()]
x=1
for i in range(1,N):
  x+=(K-1)
  if x>=N:
    print(i)
    break
Buggy python submission (verdict: Runtime Error):
x=int(input())
a=x//999
b=x%999+1000
B=text(b)
C=B[1:]
if a==0:
  print("ABC"+C)
else:
  print("ABD"+C)


Fixed submission:
x=int(input())
a=x//1000
if a==0:
  print("ABC")
else:
  print("ABD")