Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())
if A > B:
  result = "NO"
else:
  if V - W > 0:
    if B - A - T * (V - W) <= 0:
      if 
    else:
      result = "NO"
  else:
    result = "NO"
print(result)

Fixed submission:
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())
if V - W > 0:
  if abs(B - A) - T * abs(V - W) <= 0:
    result = "YES"
  else:
    result = "NO"
else:
  result = "NO"
print(result)

Buggy python submission (verdict: Runtime Error):
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())
if A > B:
  result = "YES"
elif A == B:
  result = "YES"
else:
  if V - W > 0:
    for i in range(1, T + 1):
      if B - A - i * (V - W) == 0:
        result = "YES"
        break
  else:
    result = "NO"
print(result)

Fixed submission:
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())
if V - W > 0:
  if abs(B - A) - T * abs(V - W) <= 0:
    result = "YES"
  else:
    result = "NO"
else:
  result = "NO"
print(result)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(i) for i in input().split()]
ans = 1
lim = 10 ** 18
for i in A:
  ans *= i
if ans == 0:
  print(0)
elif ans > lim:
  print(-1)
else:
  print(ans)


Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]
ans = 1
lim = 10 ** 18
if not (0 in A):
  for i in A:
    ans *= i
    if ans > lim:
      break
  if ans > lim:
    print(-1)
  else:
    print(ans)
else:
  print(0)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, c, d = map(int, input().split())
while d != 0 or a != 0:
  c -= b  # 高橋君の攻撃
  a -= d  # 青木君の攻撃
  if c == 0:
    print("Yes")
    break
  elif a == 0:
    print("No")
    break

Fixed submission:
a, b, c, d = map(int, input().split())
while d != 0 or a != 0:
  c -= b  # 高橋君の攻撃
  a -= d  # 青木君の攻撃
  if c <= 0:
    print("Yes")
    break
  elif a <= 0:
    print("No")
    break
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
K, S = map(int, input().split())
ans = 0
for i in itertools.product(range(S+1), repeat=2):
  if all([j <= K for j in i]):
    Z = S - sum(i)
    if 0 <= Z <= K:
      ans += 1
print(ans)

Fixed submission:
import itertools
K, S = map(int, input().split())
ans = 0
for i in itertools.product(range(K+1), repeat=2):
    Z = S - sum(i)
    if 0 <= Z <= K:
      ans += 1
print(ans)
# for x in range(K+1):
#  for y in range(K+1):
#    z = S - x - y
#    if 0 <= z <= K:
#      ans += 1

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
K, S = map(int, input().split())
ans = 0
for i in itertools.product(range(S+1), repeat=3):
  if sum(i) == S and all([j <= K for j in i]):
    ans += 1
print(ans)

Fixed submission:
import itertools
K, S = map(int, input().split())
ans = 0
for i in itertools.product(range(K+1), repeat=2):
    Z = S - sum(i)
    if 0 <= Z <= K:
      ans += 1
print(ans)
# for x in range(K+1):
#  for y in range(K+1):
#    z = S - x - y
#    if 0 <= z <= K:
#      ans += 1
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
ans = 1
for i in range(N):
    ans = ans * A[i]

if(ans > 10**18):
    print(-1)
else:
    print(ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
if 0 in A:
  print(0)
  exit(0)
ans = 1
for i in range(N):
    ans = ans * A[i]
    if(ans > 10**18):
        print(-1)
        exit(0)

print(ans)
Buggy python submission (verdict: Runtime Error):
X = int(input())
M = []
for i in range(119):
    M.append(i**5)
for i in range(119):
    for j in range(119):
      if(M[i] - M[j] == X):
          A = i
          B = j
      elif(M[i] + M[j] == X):
          A = i
          B = -1*j

print(A,B)


Fixed submission:
X = int(input())
M = []
for i in range(120):
    M.append(i**5)
for i in range(120):
    for j in range(120):
      if(M[i] - M[j] == X):
          A = i
          B = j
      elif(M[i] + M[j] == X):
          A = i
          B = -1*j

print(A,B)
Buggy python submission (verdict: Time Limit Exceeded):
s = str(input())
N = len(s)
array = [0]*2019
array[0] += 1
count = 0
for i in reversed(range(0, N)):
    x = s[i:N]
    y = int(x)
    array[y%2019] += 1

for i in array:
    count += i*(i-1)/2
print(int(count))


Fixed submission:
s = str(input())
N = len(s)
array = [0]*2019
array[0] += 1
count = 0
d = 1
r = 0
for i in reversed(range(0, N)):
    r = ( r + int( s[i] ) * d ) % 2019
    d = d * 10 % 2019
    array[r] += 1
for i in array:
    count += i*(i-1)/2
print(int(count))
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
li = list(map(int,input().split()))
x = sum(li) * 1/(4*M)
li.sort(reverse=True)

l = [i for i in li if i > x]
if M > len(l):
    print("No")
else:
    print("Yes")

Fixed submission:
N,M = map(int,input().split())
li = list(map(int,input().split()))
x = sum(li) / (4*M)

l = [i for i in li if i >= x]
if len(l) >= M:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
def make_divisors(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

n = int(input())
a = make_divisors(n)
b = []
for i in range(0,len(a),2):
    sum = a[i] + a[i+1]
    b.append(sum)
b.sort()
print(b[0]-2)


Fixed submission:
def make_divisors(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


n = int(input())
a = make_divisors(n)
b = []

if len(a) % 2 == 0:
    for i in range(0,len(a),2):
        sum = a[i] + a[i+1]
        b.append(sum)
else:
    b.append(a[len(a)-1]*2)
    for i in range(0,len(a)-1,2):
        sum = a[i] + a[i+1]
        b.append(sum)

b.sort()
print(b[0]-2)
Buggy python submission (verdict: Time Limit Exceeded):
L, R = map(int, input().split())
a = 2020

for i in range(L,R+1):
    for j in range(i+1,R+1):
        ans = i*j%2019
        if(a > ans):
            a = ans
        if ans == 0:
            break
print(a)


Fixed submission:
L, R = map(int, input().split())
a = 2020

if(R-L > 2019):
    R = L+2019
for i in range(L,R+1):
    for j in range(i+1,R+1):
        ans = i*j%2019
        if(a > ans):
            a = ans
print(a)

Buggy python submission (verdict: Time Limit Exceeded):
L, R = map(int, input().split())
a = 2020
for i in range(L,R+1):
    for j in range(i+1,R+1):
        ans = i*j%2019
        if(a > ans):
            a = ans
print(a)


Fixed submission:
L, R = map(int, input().split())
a = 2020

if(R-L > 2019):
    R = L+2019
for i in range(L,R+1):
    for j in range(i+1,R+1):
        ans = i*j%2019
        if(a > ans):
            a = ans
print(a)
Buggy python submission (verdict: Runtime Error):
n = int(input())
k = int(input())
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, 2001):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

for i in range(1,k+1):
    print(cmb(n-k+1,i,p) * cmb(k-1,i-1,p))


Fixed submission:
n, k = map(int, input().split())
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, 3000):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

for i in range(1,k+1):
    print((cmb(n-k+1,i,p)%p * cmb(k-1,i-1,p)%p))
Buggy python submission (verdict: Runtime Error):
a = input()
s = int(ord(a)

if  65<=s and s<=90:
 print("A")
elif 97<=s and s<=122:
 print("B")

Fixed submission:
a = input()

s=int(ord(a))

if  65<=s and s<=90:
 print("A")
elif 97<=s and s<=122:
 print("a")
Buggy python submission (verdict: Runtime Error):
import numpy as np
x,n =map(int,input().split())

if  n==0:
 print(x)
else:
 P =list(map(int,input().split()))
 l = list(range(2*x))
 result = list(set(l) - set(P))
 abs = list(np.abs(np.array(result)-x))
 abs.remove(0)
 min = min(abs)
 print(abs)
 print(result[abs.index(min)])

Fixed submission:
import numpy as np
x,n =map(int,input().split())

if  n==0:
 print(x)
else:
 P =list(map(int,input().split()))
 for i in range(100):
  if  (x-i) not in P:
   print(x-i)
   break
  elif (x+i) not in P:
   print(x+i)
   break
Buggy python submission (verdict: Time Limit Exceeded):
import sys
n = int(input())
a =[ [int(c) for c in l.split()] for l in sys.stdin]
a =a[0]
m = 1

for i in range(n):
 m=m*a[i]

if m>10**18:
 print(-1)
else:
 print(m)

Fixed submission:
import sys
n = int(input())
a =[ [int(c) for c in l.split()] for l in sys.stdin]
a =a[0]
m = 1

if (0 in a)==True:
 m=0
else:
 for i in range(n):
  m*=a[i]
  if m>10**18:
   m=-1
   break

print(m)
Buggy python submission (verdict: Runtime Error):
k = int(input())
s  = input()

if  len(s)<=k:
 print(s)
else:
print(s[:k]+'...')


Fixed submission:
k = int(input())
s  = input()
if  len(s)<=k:
 print(s)
else:
 print(s[:k]+'...')
Buggy python submission (verdict: Runtime Error):
n,k,m = map(int,input().split())
a = list(map(int,input().split()))

t = n*m - sum(a)
if 0<=t<=k:
 print(t)
if  k<t:
 print(-1)
else:
 print(0

Fixed submission:
print(chr(ord(input())+1))
Buggy python submission (verdict: Runtime Error):
A, B, K = map(int, input().split())
 
if A >= K:
  print (A - K, B)
else:
  print (0, max(0, B - (K - A)))


Fixed submission:
S,T = input().split()
print(T+S)

Buggy python submission (verdict: Runtime Error):
a,b,k = map(int,input().split())
if a>=k:
 print(a-k,b)
elif a+b<=k:
 print(0,0)
else:
 print(0,b-k+a)

Fixed submission:
S,T = input().split()
print(T+S)

Buggy python submission (verdict: Runtime Error):
S=input()
T=input()
print(T+S)

Fixed submission:
S,T = input().split()
print(T+S)
Buggy python submission (verdict: Runtime Error):
a,b = map(int,input().split())
print(a-b*2 if a-b*2>=0 0 else)

Fixed submission:
a,b = map(int,input().split())
print(a-b*2 if a-b*2>=0 else 0)
Buggy python submission (verdict: Runtime Error):
#from collections import deque
n,m=map(int,input().split())
root=[[] for _ in range(m)]
for i in range(m):
	a,b=map(int,input().split())
	root[a-1].append(b-1)
	root[b-1].append(a-1)
times=[0]*n
sign=[-1]*n
sign[0]=0
#q=deque(root[0])
flag=0
a=root[0]
b=[]
f=False
while True:
	for i in a:
		if sign[i]==-1:
			sign[i]=flag
			b.extend(root[i])
			f=True
	flag=i
	a=b
	b=[]
	if f==False:
		break
	f=False
for i in range(n-1):
	print(sign[i+1]+1)

Fixed submission:
from collections import deque
n,m=map(int,input().split())
root=[[] for _ in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	root[a-1].append(b-1)
	root[b-1].append(a-1)
times=[0]*n
sign=[-1]*n
sign[0]=0
color=[False]*n
que=deque([0])
while que: #qが空でないのはこう表現できる
	i=que.popleft()
	if color[i]==False:
		for edge in root[i]:
			if color[edge]==False and sign[edge]==-1: #相方が親じゃなければ(親ならすでに探索済みのはず)
				sign[edge]=i
				que.append(edge)
		color[i]=True
print('Yes')
for i in range(n-1):
	print(sign[i+1]+1)
Buggy python submission (verdict: Runtime Error):
n,m,x=map(int,input().split())
c=[]
a=[]
for i in range(m):
	C,*A=map(int,input().split())
	c.append(C)
	a.append(A)

ans=[]
for i in range(2**n):
	A=[0]*m
	C=0
	lst=list(map(int,format(i,'b').zfill(n)))
	for j in range(m):
		if lst[j]==1:
			C+=c[j]
			for k in range(m):
				A[k]+=a[j][k]
	if all(elem>=x for elem in A):
		ans.append(C)
if len(ans):
	print(min(ans))
else:
	print(-1)

Fixed submission:
n,m,x=map(int,input().split())
c=[]
a=[]
for i in range(n):
	C,*A=map(int,input().split())
	c.append(C)
	a.append(A)

ans=[]
for i in range(2**n):
	A=[0]*m
	C=0
	lst=list(map(int,format(i,'b').zfill(n)))
	for j in range(n):
		if lst[j]==1:
			C+=c[j]
			for k in range(m):
				A[k]+=a[j][k]
	if all(elem>=x for elem in A):
		ans.append(C)
if len(ans):
	print(min(ans))
else:
	print(-1)
Buggy python submission (verdict: Runtime Error):
n,*abc=map(int,input().split())
ip=[0]*n
for i in range(n):
	tmp=input()
	if tmp=="AB":
		ip[i]=[0,1]
	elif tmp=="BC":
		ip[i]=[1,2]
	else:
		ip[i]=[0,2]
ans="Yes"
res=[0]*n
s=sum(abc)
if s==0:
	ans="No"
elif s==1:
	for i in range(n):
		i1=ip[i][0]
		i2=ip[i][1]
		ABC=(i1,i2)
		if ABC==(0,0):
			ans="No"
		'''
		if abc[i1]+abc[i2]==0:
			ans="No"
		'''
		elif abc[i1]+abc[i2]==1:
			if abc[i1]==0:
				abc[i1]+=1
				abc[i2]-=1
				res[i]=i1
			else:
				abc[i1]-=1
				abc[i2]+=1
				res[i]=i2
else:
	i1=ip[0][0]
	i2=ip[0][1]
	if abc[i1]+abc[i2]==0:
		ans="No"
	else:
		for i in range(n):
			i1=ip[i][0]
			i2=ip[i][1]
			if abc[i1]*abc[i2]==0:
				if abc[i1]==0:
					abc[i1]+=1
					abc[i2]-=1
					res[i]=i1
				else:
					abc[i1]-=1
					abc[i2]+=1
					res[i]=i2
			elif i+1<n and ip[i+1]!=ip[i]:
				c=list(set(ip[i])&set(ip[i+1]))[0]
				if i1==c:
					abc[i1]+=1
					abc[i2]-=1
					res[i]=i1
				else:
					abc[i1]-=1
					abc[i2]+=1
					res[i]=i2
			else:
				abc[i1]+=1
				abc[i2]-=1
				res[i]=i1
print(ans)
dic={0:"A",1:"B",2:"C"}
if ans=="Yes":
	for i in range(n):
		print(dic[res[i]])
		'''
		if res[i]==0:
			print("A")
		elif res[i]==1:
			print("B")
		else:
			print("C")
		'''

Fixed submission:
n,*abc=map(int,input().split())
ip=[0]*n
for i in range(n):
	tmp=input()
	if tmp=="AB":
		ip[i]=[0,1]
	elif tmp=="BC":
		ip[i]=[1,2]
	else:
		ip[i]=[0,2]
ans="Yes"
res=[0]*n
s=sum(abc)
if s==0:
	ans="No"
elif s==1:
	for i in range(n):
		i1=ip[i][0]
		i2=ip[i][1]
		if abc[i1]+abc[i2]==0:
			ans="No"
		elif abc[i1]+abc[i2]==1:
			if abc[i1]==0:
				abc[i1]+=1
				abc[i2]-=1
				res[i]=i1
			else:
				abc[i1]-=1
				abc[i2]+=1
				res[i]=i2
else:
	i1=ip[0][0]
	i2=ip[0][1]
	if abc[i1]+abc[i2]==0:
		ans="No"
	else:
		for i in range(n):
			i1=ip[i][0]
			i2=ip[i][1]
			if abc[i1]*abc[i2]==0:
				if abc[i1]==0:
					abc[i1]+=1
					abc[i2]-=1
					res[i]=i1
				else:
					abc[i1]-=1
					abc[i2]+=1
					res[i]=i2
			elif i+1<n and ip[i+1]!=ip[i]:
				c=list(set(ip[i])&set(ip[i+1]))[0]
				if i1==c:
					abc[i1]+=1
					abc[i2]-=1
					res[i]=i1
				else:
					abc[i1]-=1
					abc[i2]+=1
					res[i]=i2
			else:
				if abc[i1]>=abc[i2]:
					abc[i1]+=1
					abc[i2]-=1
					res[i]=i1
				else:
					abc[i1]-=1
					abc[i2]+=1
					res[i]=i2
print(ans)
if ans=="Yes":
	for i in range(n):
		if res[i]==0:
			print("A")
		elif res[i]==1:
			print("B")
		else:
			print("C")
Buggy python submission (verdict: Time Limit Exceeded):
n,k,c=map(int,input().split())
s=list(input())
for i in range(len(s)):
	if s[i]=="x":
		s[i]=False
	else:
		s[i]=True
i=0
work=[]
while len(work)<k:
	if s[i]:
		work.append(i)
		i+=c+1
	else:
		i+=1
#print(work)

for day in work:
	s0=s[:]
	s0[day]=False
	i=0
	cnt=0
	while i<n:
		if s0[i]:
			i+=c+1
			cnt+=1
		else:
			i+=1
	if cnt<k:
		print(day+1)

Fixed submission:
n,k,c=map(int,input().split())
s=list(input())
for i in range(len(s)):
	if s[i]=="o":
		s[i]=True
	else:
		s[i]=False
i=0
work1=[]
while len(work1)<k:
	if s[i]:
		work1.append(i)
		i+=c+1
	else:
		i+=1
i=n-1
work2=[]
while len(work2)<k:
	if s[i]:
		work2.append(i)
		i-=c+1
	else:
		i-=1
work2.sort()
for i in range(k):
	if work1[i]==work2[i]:
		print(work1[i]+1)
Buggy python submission (verdict: Time Limit Exceeded):
#約数全列挙
def make_divisors(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


n=int(input())
#n%k!=0
cnt=len(make_divisors(n-1))

#n%k==0
lst=make_divisors(n)
for k in lst:
	t=n
	while t%k==0:
		t//=k
	t%=k
	if  t==1:
		cnt+=1
print(cnt-1)

Fixed submission:
#約数全列挙
def make_divisors(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


n=int(input())
#n%k!=0
cnt=len(make_divisors(n-1))-1

#n%k==0
lst=make_divisors(n)
for k in lst:
	if k!=1:
		t=n
		while t%k==0:
			t//=k
		if (t-1)%k==0:
			cnt+=1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
n,x,y=map(int,input().split())
x-=1
y-=1
def dist(a,b):
	return min(abs(b-a),1+abs(a-x)+abs(b-y),1+abs(b-x)+abs(a-y))
#d==1
print(n)
for d in range(2,n):
	ans=0
	for i in range(n-d):
		lst=[]
		if i+d<n and dist(i,i+d)==d:
			lst.append(i+d)
		d0=d
		d0-=abs(x-i)
		d0-=1
		if d0>=0:
			if i<y-d0 and dist(i,y-d0)==d:
				lst.append(y-d0)
			if i<y+d0 and dist(i,y+d0)==d and y+d0<n:
				lst.append(y+d0)
		ans+=len(list(set(lst)))
	print(ans)

Fixed submission:
n,x,y=map(int,input().split())
x-=1
y-=1
def dist(a,b):
	return min(abs(b-a),1+abs(a-x)+abs(b-y),1+abs(b-x)+abs(a-y))
#d==1
print(n)
for d in range(2,n):
	ans=0
	for i in range(n-d):
		lst=[]
		if i+d<n and dist(i,i+d)==d:
			lst.append(i+d)
		d0=d
		d0-=abs(x-i)
		d0-=1
		if d0>=0:
			if i<y-d0 and dist(i,y-d0)==d:
				lst.append(y-d0)
			if i<y+d0 and dist(i,y+d0)==d and y+d0<n:
				lst.append(y+d0)
		ans+=len(list(set(lst)))
	print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
p=list(map(int, input().split()))
for i in range(n):
	p[i]=(1+p[i])/2
ans=0
for i in range(n-k+1):
	ans=max(ans,sum(p[i:i+k]))
print('{:.8f}'.format(ans))

Fixed submission:
n,k=map(int,input().split())
p=list(map(int, input().split()))
for i in range(n):
	p[i]=(1+p[i])/2
cs=[]
sum=0
for i in range(n):
	sum+=p[i]
	cs.append(sum)
ans=cs[k-1]
for i in range(1,n-k+1):
	ans=max(ans,cs[i+k-1]-cs[i-1])
print('{:.8f}'.format(ans))
Buggy python submission (verdict: Runtime Error):
a,b,k=map(int,input().split())
if a<k:
	b=max(b-(k-a),0)
	a=0
else:
	a=a-k
print(a,end=' ')
print(b)

Fixed submission:
s,t=input().split()
print(t+s)
Buggy python submission (verdict: Runtime Error):
#降順ソートの方がうまくいきそう
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())),reverse=True)
cs=[]
sum=0
for i in range(n):
	sum+=a[i]
	cs.append(sum)

#和が引数以上の場合をカウントする
def overX(x):
	count=0
	#両手が違う人を握るときのみ考える
	if a[0]*2<x:
		return 0
	else:
		for i in range(n):
			if a[i]+a[0]<x:
				count+=0
			else:
				lb, ub = 0, n
				#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
				while ub-lb>1:
					mid=(lb+ub)//2
					if a[i]+a[mid]>=x:
						lb=mid
					else:
						ub=mid
				count+=lb+1
		return count
#print(overX(130))

#overX>=mなる最大のxを探す->xは小さい方が実現しやすいのでパターンA->[lb,ub)でもつ
lb=1 #実現しやすい方
ub=2*10**5
while ub-lb>1:
	mid=(ub+lb)//2
	if overX(mid)>=m:
		lb=mid
	else:
		ub=mid
#ub=overX(x)>=mなる最小のx。これ以上大きくするとmに満たなくなる。
maxx=lb

hp=0
#maxx+1以上の要素をすべてたす
#和がmaxx+1以上になる組み合わせの数だけhpを加え、countをインクリメントする
if a[0]*2>=maxx+1:
	for i in range(n):
		if a[i]+a[0]<maxx+1:
			break
		else:
			lb, ub = 0, n
			#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
			while ub-lb>1:
				mid=(lb+ub)//2
				if a[i]+a[mid]>=maxx+1:
					lb=mid
				else:
					ub=mid
			#a[0]からa[lb]は、a[i]と足した時にx以上になり条件を満たす。
			hp+=a[i]*(lb+1)+cs[lb]
hp+=(m-overX(maxx+1))*maxx
print(hp)

Fixed submission:
n,k=map(int,input().split())
r,s,p=map(int,input().split())
t=input()
points=0
renzoku=[1 for i in range(k)]
for i in range(n):
	if i<k:
		if t[i]=='r':
			points+=p
		if t[i]=='s':
			points+=r
		if t[i]=='p':
			points+=s
	else:
		if t[i]==t[i-k]:
			renzoku[i%k]+=1
			if renzoku[i%k]%2==1:
				if t[i]=='r':
					points+=p
				if t[i]=='s':
					points+=r
				if t[i]=='p':
					points+=s
		else:
			renzoku[i%k]=1
			if t[i]=='r':
				points+=p
			if t[i]=='s':
				points+=r
			if t[i]=='p':
				points+=s
print(points)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
#降順ソートの方がうまくいきそう
n,m=map(int,input().split())
a=np.sort(np.array(list(map(int,input().split()))))[::-1]
cs=np.cumsum(a)

#和が引数以上の場合をカウントする
def overX(x):
	count=0
	#両手が違う人を握るときのみ考える
	if a[0]*2<x:
		return 0
	else:
		for i in range(n):
			if a[i]+a[0]<x:
				count+=0
			else:
				lb, ub = 0, n
				#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
				while ub-lb>1:
					mid=(lb+ub)//2
					if a[i]+a[mid]>=x:
						lb=mid
					else:
						ub=mid
				count+=lb+1
		return count
#print(overX(130))

#overX>=mなる最大のxを探す->xは小さい方が実現しやすいのでパターンA->[lb,ub)でもつ
lb=1 #実現しやすい方
ub=2*10**5
while ub-lb>1:
	mid=(ub+lb)//2
	if overX(mid)>=m:
		lb=mid
	else:
		ub=mid
#ub=overX(x)>=mなる最小のx。これ以上大きくするとmに満たなくなる。
maxx=lb

hp=0
#maxx+1以上の要素をすべてたす
#和がmaxx+1以上になる組み合わせの数だけhpを加え、countをインクリメントする
if a[0]*2>=maxx+1:
	for i in range(n):
		if a[i]+a[0]<maxx+1:
			break
		else:
			lb, ub = 0, n
			#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
			while ub-lb>1:
				mid=(lb+ub)//2
				if a[i]+a[mid]>=maxx+1:
					lb=mid
				else:
					ub=mid
			#a[0]からa[lb]は、a[i]と足した時にx以上になり条件を満たす。
			hp+=a[i]*(lb+1)+cs[lb]
'''print(hp)
print(overX(maxx))
print(overX(maxx+1))
print(maxx)'''
hp+=(m-overX(maxx+1))*maxx
print(hp)

Fixed submission:
#降順ソートの方がうまくいきそう
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())),reverse=True)
cs=[]
sum=0
for i in range(n):
	sum+=a[i]
	cs.append(sum)

#和が引数以上の場合をカウントする
def overX(x):
	count=0
	#両手が違う人を握るときのみ考える
	if a[0]*2<x:
		return 0
	else:
		for i in range(n):
			if a[i]+a[0]<x:
				count+=0
			else:
				lb, ub = 0, n
				#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
				while ub-lb>1:
					mid=(lb+ub)//2
					if a[i]+a[mid]>=x:
						lb=mid
					else:
						ub=mid
				count+=lb+1
		return count
#print(overX(130))

#overX>=mなる最大のxを探す->xは小さい方が実現しやすいのでパターンA->[lb,ub)でもつ
lb=1 #実現しやすい方
ub=2*10**5+1
while ub-lb>1:
	mid=(ub+lb)//2
	if overX(mid)>=m:
		lb=mid
	else:
		ub=mid
#ub=overX(x)>=mなる最小のx。これ以上大きくするとmに満たなくなる。
maxx=lb

hp=0
#maxx+1以上の要素をすべてたす
#和がmaxx+1以上になる組み合わせの数だけhpを加え、countをインクリメントする
if a[0]*2>=maxx+1:
	for i in range(n):
		if a[i]+a[0]<maxx+1:
			break
		else:
			lb, ub = 0, n
			#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
			while ub-lb>1:
				mid=(lb+ub)//2
				if a[i]+a[mid]>=maxx+1:
					lb=mid
				else:
					ub=mid
			#a[0]からa[lb]は、a[i]と足した時にx以上になり条件を満たす。
			hp+=a[i]*(lb+1)+cs[lb]
hp+=(m-overX(maxx+1))*maxx
print(hp)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int, input().split()))
for i in range(n):
	a[i]=format(a[i],'b')
#count1に1をカウントして入れる
#popは右側に行うとはやいらしいので気にせず行う
total=0
count1=0
for k in range(60):
	count1=0
	for i in range(n):
		if k<len(a[i]):
			if a[i][-1-k]=='1':
				count1+=1
	total+=count1*(n-count1)*(2**k)
	total=total%(10**9+7)
print(total)

Fixed submission:
n=int(input())
a=list(map(int, input().split()))
for i in range(n):
	a[i]=format(a[i],'b')
#count1に1をカウントして入れる
#popは右側に行うとはやいらしいので気にせず行う
total=0
count1=0
for k in range(60):
	count1=0
	for i in range(n):
		if k<len(a[i]):
			if a[i][-1-k]=='1':
				count1+=1
	total+=count1*(n-count1)*(2**k)
	total=total%(10**9+7)
print(total)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input()
keys=set()
keys.add(s[0:3])
for i in range(3,n):
	adkeys=set()
	for key in keys:
		adkeys.add(key[0]+key[1]+s[i])
		adkeys.add(key[0]+key[2]+s[i])
		adkeys.add(key[1]+key[2]+s[i])
	keys=keys|adkeys
print(len(keys))

Fixed submission:
n=int(input())
s=input()
numbers=[str(i).zfill(3) for i in range(1000)]

count=0
for num in numbers:
	j=0
	for i in range(n):
		if num[j]==s[i]:
			j+=1
		if j==3:
			break
	if j==3:
		count+=1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input()
import itertools
print(len(set(itertools.combinations(list(s),3))))

Fixed submission:
n=int(input())
s=input()
numbers=[str(i).zfill(3) for i in range(1000)]

count=0
for num in numbers:
	j=0
	for i in range(n):
		if num[j]==s[i]:
			j+=1
		if j==3:
			break
	if j==3:
		count+=1
print(count)