Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
s=list(input())
q=int(input())
sc=0
for _ in range(q):
  query=input()
  if query=="1":
    sc+=1
  else:
    t,f,c=query.split()
    if f=="1":
      if sc%2==0:
        s=[c]+s
      else:
        s=s+[c]
    else:
      if sc%2==0:
        s=s+[c]
      else:
        s=[c]+s
if sc%2!=0:
  s.reverse()
print("".join(s))

Fixed submission:
s=list(input())
q=int(input())
sc=0
lhs=[]
rhs=[]
for _ in range(q):
  query=input()
  if query=="1":
    sc+=1
  else:
    t,f,c=query.split()
    if f=="1":
      if sc%2==0:
        lhs.append(c)
      else:
        rhs.append(c)
    else:
      if sc%2==0:
        rhs.append(c)
      else:
        lhs.append(c)

lhs.reverse()
s=lhs+s+rhs
if sc%2!=0:
  s.reverse()
print("".join(s))

Buggy python submission (verdict: Time Limit Exceeded):
s=list(input())
q=int(input())
for _ in range(q):
  query=input()
  if query=="1":
    s.reverse()
  else:
    t,f,c=query.split()
    if f=="1":
      s=[c]+s
    else:
      s=s+[c]
    
print("".join(s))

Fixed submission:
s=list(input())
q=int(input())
sc=0
lhs=[]
rhs=[]
for _ in range(q):
  query=input()
  if query=="1":
    sc+=1
  else:
    t,f,c=query.split()
    if f=="1":
      if sc%2==0:
        lhs.append(c)
      else:
        rhs.append(c)
    else:
      if sc%2==0:
        rhs.append(c)
      else:
        lhs.append(c)

lhs.reverse()
s=lhs+s+rhs
if sc%2!=0:
  s.reverse()
print("".join(s))
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
nega=[i for i in a if i<0]
zera=[i for i in a if i==0]
posa=[i for i in a if i>0]

def cnt(x):
  y=0
  if x>=0:
    y+=n*len(zera)
  
  for i in posa:
    y+=len([j for j in a if j*i<=x])
  
  for i in nega:
    y+=len([j for j in a if j*i<=x])
  
  y-=len([j for j in a if j*j<=x])
  return y//2

r=10**18
l=-r-1
while r-l>1:
  c=(r+l)//2
  if cnt(c)>=k:
    r=c
  else:
    l=c
print(r)

Fixed submission:
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a)
a.sort()
nega=a[a<0]
zera=a[a==0]
posa=a[a>0]

def cnt(x):
  y=0
  if x>=0:
    y+=n*len(zera)
  y+=np.searchsorted(a,x//posa,side="right").sum()
  y+=n*len(nega)-np.searchsorted(a,-(-x//nega)).sum() 
  y-=len(a[a*a<=x])
  return y//2

r=10**18
l=-r-1
while r-l>1:
  c=(r+l)//2
  if cnt(c)>=k:
    r=c
  else:
    l=c
print(r)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
nega=[i for i in a if i<0]
zera=[i for i in a if i==0]
posa=[i for i in a if i>0]

def cnt(x):
  y=0
  if x>=0:
    y+=n*len(zera)
  
  for i in posa:
    y+=len([j for j in a if j*i<=x])
  
  y+=n*len(nega)
  
  for i in nega:
    y-=len([j for j in a if j*i>x])
  
  y-=len([j for j in a if j*j<=x])
  return y//2

r=10**18
l=-r-1
while r-l>1:
  c=(r+l)//2
  if cnt(c)>=k:
    r=c
  else:
    l=c
print(r)

Fixed submission:
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a)
a.sort()
nega=a[a<0]
zera=a[a==0]
posa=a[a>0]

def cnt(x):
  y=0
  if x>=0:
    y+=n*len(zera)
  y+=np.searchsorted(a,x//posa,side="right").sum()
  y+=n*len(nega)-np.searchsorted(a,-(-x//nega)).sum() 
  y-=len(a[a*a<=x])
  return y//2

r=10**18
l=-r-1
while r-l>1:
  c=(r+l)//2
  if cnt(c)>=k:
    r=c
  else:
    l=c
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=0
for i in range(n-k+1):
  cnt=0
  for j in range(i,i+k):
    cnt+=(1/p[j])*(p[j]*(1+p[j])/2)
  ans=max(ans,cnt)
  
print(ans)

Fixed submission:
n,k=map(int,input().split())
p=list(map(int,input().split()))
e=[]
for i in range(n):
  e.append((1/p[i])*(p[i]*(1+p[i])/2))

a=0
for i in range(k):
  a+=e[i]

ans=[a]
for i in range(1,n-k+1):
  a=a-e[i-1]+e[i+k-1]
  ans.append(a)

print(max(ans))
Buggy python submission (verdict: Runtime Error):
from fractions import gcd

n,m=map(int,input().split())
a=list(map(int,input().split()))
a=list(set(a))

a=list(map(lambda x: x//2, a))

def lcm(q):
  x = q[0]
  for i in range(1, len(q)):
    x = (x * q[i]) // gcd(x, q[i])
  return x

lcma=lcm(a)

if (lcma//a[0])%2==0:
  print(0)
  
else:
  flg=0
  for i in range(1,n):
    if (lcma//a[i])%2==0:
      print(0)
      flg=1

  if flg==0:
    temp=m//lcma
    print(temp//2 if temp%2==0 else temp//2+1)

Fixed submission:
from fractions import gcd

n,m=map(int,input().split())
a=list(map(int,input().split()))
a=list(set(a))

a=list(map(lambda x: x//2, a))

def lcm(q):
  x = q[0]
  for i in range(1, len(q)):
    x = (x * q[i]) // gcd(x, q[i])
  return x

lcma=lcm(a)

if (lcma//a[0])%2==0:
  print(0)
else:
  flg=0
  for i in range(1,len(a)):
    if (lcma//a[i])%2==0:
      print(0)
      flg=1
      break
  if flg==0:
    temp=m//lcma
    print(temp//2 if temp%2==0 else temp//2+1)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
M=10**9+7
each=[]
for i in range(n-1):
  for j in range(i+1,n):
    each.append(a[i]^a[j])
print(sum(each)%M)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
M=10**9+7

ans = 0
for i in range(61):
  ones=sum([1 for a in A if (a>>i)&1])
  ans += (1<<i)*ones*(N-ones)
  ans %= M

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
M=10**9+7
each=[]
for i in range(n-1):
  for j in range(i+1,n):
    each.append((a[i]^a[j])%M)
print(sum(each)%M)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
M=10**9+7

ans = 0
for i in range(61):
  ones=sum([1 for a in A if (a>>i)&1])
  ans += (1<<i)*ones*(N-ones)
  ans %= M

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
M=10**9+7
s=0
for i in range(n-1):
  for j in range(i+1,n):
    s+=(a[i]^a[j])%M
print(s%M)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
M=10**9+7

ans = 0
for i in range(61):
  ones=sum([1 for a in A if (a>>i)&1])
  ans += (1<<i)*ones*(N-ones)
  ans %= M

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
M=10**9+7
s=0
for i in range(n-1):
  for j in range(i+1,n):
    s+=a[i]^a[j]
print(s%M)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
M=10**9+7

ans = 0
for i in range(61):
  ones=sum([1 for a in A if (a>>i)&1])
  ans += (1<<i)*ones*(N-ones)
  ans %= M

print(ans)
Buggy python submission (verdict: Runtime Error):
from math import sqrt
from itertools import permutations
N=int(input())
xy=[list(map(int,input().split())) for _ in range(N)]
ans=0
cnt=0
for i in permutations(range(3)):
  d=0
  for j in range(N-1):
    dx=xy[i[j+1]][0]-xy[i[j]][0]
    dy=xy[i[j+1]][1]-xy[i[j]][1]
    d+=sqrt(dx**2+dy**2)
  ans+=d
  cnt+=1
print(ans/cnt)

Fixed submission:
import itertools
from math import *
n=int(input())
ps=[list(map(int,input().split())) for _ in range(n)]
perms = list(itertools.permutations(ps, n))
dists = []
for i in range(len(perms)):
  dist = 0
  cur = perms[i][0]
  for j in range(1,len(perms[i])):
    d = sqrt((perms[i][j][0]-cur[0]) ** 2 + (perms[i][j][1]-cur[1])**2)
    cur = perms[i][j]
    dist += d

  dists.append(dist)
print(sum(dists)/len(perms))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
N=int(input())
L=sorted(list(map(int,input().split())))
cmb=list(combinations(L,3))
cnt=0
for i in range(len(cmb)):
  if cmb[i][0]+cmb[i][1]>cmb[i][2]:
    cnt+=1
print(cnt)

Fixed submission:
from bisect import bisect_left
n=int(input())
l=sorted(list(map(int,input().split())))
cnt=0
for i in range(n-2):
  for j in range(i+1,n-1):
    cnt+=bisect_left(l,l[i]+l[j])-j-1
print(cnt)
Buggy python submission (verdict: Runtime Error):
SR=S+[S[0]]
cnt=0
for i in range(len(S)-1):
  if SR[i]==SR[i+1]==SR[i+2]:
    SR[i+1]=0
    cnt+=1

for i in range(len(S)):
  if SR[i]==SR[i+1]:
    SR[i]=0
    cnt+=1
    
if SR[-2]==0 and S[-1]!=S[-2]:
  ans = cnt*K-1
else:
  ans = cnt*K
print(ans)

Fixed submission:
s=list(input())
k=int(input())

if len(set(s))==1:
  print((len(s)*k)//2)
  exit()

t=[1]
for i in range(1,len(s)):
  if s[i-1]==s[i]:
    t[-1]+=1
  else:
    t.append(1)
    
ans=0
for i in t:
  ans+=(i//2)*k

if s[0]==s[-1]:
  ans+= ((t[0]+t[-1])//2 - (t[0]//2+t[-1]//2))*(k-1)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
for i in range(1,m+1):
  a[-1]=a[-1]//2
  a.sort()

print(sum(a))

Fixed submission:
import heapq
n,m = map(int,input().split())
a = list(map(lambda x: (-1)*int(x),input().split()))
heapq.heapify(a)

for i in range(1,m+1):
  t=heapq.heappop(a)
  heapq.heappush(a,-(-t//2))

print(-sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
for i in range(m):
  a[-1] = a[-1]//2
  a.sort()
  if a[-1] == 0:
    break
print(sum(a))

Fixed submission:
import heapq
n,m = map(int,input().split())
a = list(map(lambda x: (-1)*int(x),input().split()))
heapq.heapify(a)

for i in range(1,m+1):
  t=heapq.heappop(a)
  heapq.heappush(a,-(-t//2))

print(-sum(a))
Buggy python submission (verdict: Runtime Error):
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD=10**9+7
n,m=map(int,input().split())
a=set([int(input()) for _ in range(m)])
if 1 in a:
  ans=[1,0]
else:
  ans=[1,1]

@lru_cache(maxsize=None)
def cnt(x):
  if x<2:
    return ans[x]
  if x in a:
    return 0
  else:
    return (cnt(x-1)+cnt(x-2))%MOD

print(cnt(n))

Fixed submission:
MOD=10**9+7
N,K=map(int,input().split())
A=list(map(int,input().split()))
ans=0
for i in range(N-1):
  for j in range(i+1,N):
    if A[i]>A[j]:
      ans+=((K+1)*K//2)%MOD
    elif A[i]<A[j]:
      ans+=(K*(K-1)//2)%MOD

print(ans%MOD)
Buggy python submission (verdict: Runtime Error):
N = int(input())
v = list(map(int,input().split()))
while len(v) > 2:
  temp = []
  for i in range(len(v)//2):
    temp.append((v[2*i] + v[2*i + 1])/2)
  if n % 2 == 0:
    v = temp
  else:
    temp.append(v[-1])
    v = temp
      
print(v[0]) 

Fixed submission:
N = int(input())
v = list(map(int,input().split()))
v.sort(reverse = True)

while len(v) > 1:
  x = v.pop()
  v[-1] = (x + v[-1]) /2
      
print(v[0])

Buggy python submission (verdict: Runtime Error):
N = int(input())
v = list(map(int,input().split()))
while len(v) > 1:
  x = v.pop()
  v[-1] = (v[-1] + x)/2

print(v[0]) 

Fixed submission:
N = int(input())
v = list(map(int,input().split()))
v.sort(reverse = True)

while len(v) > 1:
  x = v.pop()
  v[-1] = (x + v[-1]) /2
      
print(v[0])
Buggy python submission (verdict: Runtime Error):
s=list(input())
D=[s[0]]
i=0
while i < len(s) - 1:
  if s[i+1] == D[-1]:
    D.append(s[i+1]+s[i+2])
    i+=2
  else:
    D.append(s[i + 1])
    i+=1

print(len(D)-(1 if i == len(s) else 0))

Fixed submission:
s=list(input())
D=[s[0]]
i=0
while i < len(s) - 1:
  if s[i+1] == D[-1]:
    D.append(s[i+1:i+3])
    i+=2
  else:
    D.append(s[i + 1])
    i+=1

print(len(D)-(1 if i == len(s) else 0))

Buggy python submission (verdict: Runtime Error):
s=list(input())
n=len(s)
D=[s[-1]]
s.pop()
while len(s)>0:
  if len(D[-1])==2 or (D[-1]!=s[-1] and (len(s)==1 or s[-1]!=s[-2])):
    D.append(s[-1])
    s.pop()
  else:
    D.append(s[-2]+s[-1])
    s.pop()
    s.pop()

print(len(D))


Fixed submission:
s=list(input())
D=[s[0]]
i=0
while i < len(s) - 1:
  if s[i+1] == D[-1]:
    D.append(s[i+1:i+3])
    i+=2
  else:
    D.append(s[i + 1])
    i+=1

print(len(D)-(1 if i == len(s) else 0))

Buggy python submission (verdict: Runtime Error):
s=list(input())
n=len(s)
D=[s[0]]
s.pop(0)
while len(s)>0:
  if len(D[-1])==2 or (D[-1]!=s[0] and (len(s)==1 or s[0]!=s[1])):
    D.append(s[0])
    s.pop(0)
  else:
    D.append(s[0]+s[1])
    s.pop(0)
    s.pop(0)

print(len(D))

Fixed submission:
s=list(input())
D=[s[0]]
i=0
while i < len(s) - 1:
  if s[i+1] == D[-1]:
    D.append(s[i+1:i+3])
    i+=2
  else:
    D.append(s[i + 1])
    i+=1

print(len(D)-(1 if i == len(s) else 0))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

N = int(input())
s = [input() for _ in range(N)]

comb = itertools.combinations(s,2)

cnt = 0
for x,y in comb:
  x = list(x)
  x.sort()
  y = list(y)
  y.sort()
  if x == y:
    cnt += 1

print(cnt)

Fixed submission:
from collections import Counter
from math import factorial

N = int(input())
s = [input() for _ in range(N)]

for i in range(N):
  s[i] = list(s[i])
  s[i].sort()
  s[i] = "".join(s[i])
  
x = Counter(s).most_common()
cnt = 0
for i in range(len(x)):
  if x[i][1] >1:
    cnt += factorial(x[i][1]) // 2 // factorial(x[i][1] -2)
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
import collections
import itertools

N = int(input())
s = [input() for _ in range(N)]

comb = itertools.combinations(s,2)

cnt = 0
for x,y in comb:
  if collections.Counter(x) == collections.Counter(y):
    cnt += 1

print(cnt)

Fixed submission:
from collections import Counter
from math import factorial

N = int(input())
s = [input() for _ in range(N)]

for i in range(N):
  s[i] = list(s[i])
  s[i].sort()
  s[i] = "".join(s[i])
  
x = Counter(s).most_common()
cnt = 0
for i in range(len(x)):
  if x[i][1] >1:
    cnt += factorial(x[i][1]) // 2 // factorial(x[i][1] -2)
print(cnt)
Buggy python submission (verdict: Runtime Error):
import heapq
n,m=map(int,input().split())
ab=[[] for _ in range(m+1)]
for i in range(n):
  a,b=map(int,input().split())
  if a<=m:
    a[i].append(-b)

cand=[]
heapq.heapify(cand)
ans=0
for i in range(1,m+1):
  for j in range(len(ab[i])):
    heapq.heappush(cand,ab[i][j])
  if len(cand)>0:
    ans-=heapq.heappop(cand)

print(ans)

Fixed submission:
import heapq
n,m=map(int,input().split())
ab=[[] for _ in range(m+1)]
for i in range(n):
  a,b=map(int,input().split())
  if a<=m:
    ab[a].append(-b)

cand=[]
heapq.heapify(cand)
ans=0
for i in range(1,m+1):
  for j in range(len(ab[i])):
    heapq.heappush(cand,ab[i][j])
  if len(cand)>0:
    ans-=heapq.heappop(cand)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import heapq
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
ab=np.array(ab)
cand=[]
ans=0
for i in range(1,m+1):
  t=ab[ab[:,0]==i][:,1].tolist()
  for j in range(len(t)):
    heapq.heappush(cand,-t[j])
  if len(cand)==0:
    continue
  ans-=heapq.heappop(cand)

print(ans)

Fixed submission:
import heapq
n,m=map(int,input().split())
ab=[[] for _ in range(m+1)]
for i in range(n):
  a,b=map(int,input().split())
  if a<=m:
    ab[a].append(-b)

cand=[]
heapq.heapify(cand)
ans=0
for i in range(1,m+1):
  for j in range(len(ab[i])):
    heapq.heappush(cand,ab[i][j])
  if len(cand)>0:
    ans-=heapq.heappop(cand)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]
for i in range(N):
  temp = A[:i] + A[i+1:]
  print(max(temp))

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]

maxv = max(A)
max_id = A.index(maxv)
second = max(A[:max_id] + A[max_id+1:])

for i in range(N):
  if i == max_id:
    print(second)
  else:
    print(maxv)
Buggy python submission (verdict: Time Limit Exceeded):
L,R = map(int,input().split())

minv = 2019
for i in range(L,R):
  for j in range(i+1,R+1):
    x = i % 2019
    y = j % 2019
    val = (x * y) % 2019
    if minv > val:
      minv = val
    
print(minv)

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

if R - L > 2019:
  print(0)
else:
  minv = 2018 * 2018
  for i in range(L,R):
    for j in range(i+1,R+1):
      x = i % 2019
      y = j % 2019
      val = (x * y) % 2019
      if minv > val:
        minv = val
  print(minv)

Buggy python submission (verdict: Time Limit Exceeded):
L,R = map(int,input().split())

rem = []
for i in range(L,R):
  for j in range(i+1,R+1):
    x = i % 2019
    y = j % 2019
    val = (x * y) % 2019
    rem.append(val)
    
print(min(rem))

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

if R - L > 2019:
  print(0)
else:
  minv = 2018 * 2018
  for i in range(L,R):
    for j in range(i+1,R+1):
      x = i % 2019
      y = j % 2019
      val = (x * y) % 2019
      if minv > val:
        minv = val
  print(minv)
Buggy python submission (verdict: Runtime Error):
import numpy as np
n=int(input())
y=list(map(int,input().split()))
y=list(map(lambda x: x*2,y))
A=np.zeros((n,n),dtype='int')
for i in range(n-1):
  for j in range(i,i+2):
    A[i][j]=1
A[n-1][0],A[n-1][n-1]=1,1
b=np.linalg.solve(A,y)
print(*b)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b=[sum(a)-2*sum(a[1:n-1:2])]
for i in range(1,n):
  b.append(2*a[i-1]-b[-1])
print(*b)

Buggy python submission (verdict: Runtime Error):
import numpy as np
n=int(input())
y=list(map(int,input().split()))
y=list(map(lambda x: x*2,y))
A=np.zeros((n,n),dtype='int')
for i in range(n-1):
  for j in range(i,i+2):
    A[i][j]=1
A[n-1][0],A[n-1][n-1]=1,1
b=list(map(int,np.linalg.solve(A,y)))
print(*b)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b=[sum(a)-2*sum(a[1:n-1:2])]
for i in range(1,n):
  b.append(2*a[i-1]-b[-1])
print(*b)
Buggy python submission (verdict: Runtime Error):
s = list(input())
t = list(set(s))
if s.count(t[0]) == s.count(t[1]):
  print("Yes")
else:
  print("No")

Fixed submission:
s = list(input())
t = list(set(s))
if len(t) == 2 and s.count(t[0]) == s.count(t[1]):
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Time Limit Exceeded):
h,w=map(int,input().split())
g=[['#']*(w+2)]
for _ in range(h):
  g.append(list('#'+input()+'#'))
g.append(['#']*(w+2))

ans=0
for i in range(1,h+1):
  for j in range(1,w+1):
    c=0
    if g[i][j]=='.':
      c+=1
      u,d,r,l=0,0,0,0
      while g[i-(u+1)][j]=='.':
        u+=1
        c+=1
      while g[i+(d+1)][j]=='.':
        d+=1
        c+=1
      while g[i][j-(l+1)]=='.':
        l+=1
        c+=1
      while g[i][j+(r+1)]=='.':
        r+=1
        c+=1
    ans=max(ans,c)
print(ans)

Fixed submission:
import numpy as np

h,w=map(int,input().split())
g = np.array([list(input()) for _ in range(h)])
g = np.where(g=='.',1,0)

l = np.zeros((h,w),dtype=np.int)
r = np.zeros((h,w),dtype=np.int)
u = np.zeros((h,w),dtype=np.int)
d = np.zeros((h,w),dtype=np.int)

for i in range(w):
  l[:,i] = (l[:,i-1]+1)*g[:,i]
  r[:,-i-1] = (r[:,-i]+1)*g[:,-i-1]

for i in range(h):
  u[i,:]=(u[i-1,:]+1)*g[i,:]
  d[-i-1,:]=(d[-i,:]+1)*g[-i-1,:]

print(np.max(l+r+u+d)-3)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
a=list(map(int,input().split()))
bc=[]
for _ in range(m):
  bc.append(list(map(int,input().split())))

for i in bc:
  a.sort()
  b,c=i[0],i[1]
  for j in range(i[0]):
    if a[j]<i[1]:
      a[j]=i[1]

print(sum(a))

Fixed submission:
n,m = map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)

for b,c in bc:
  a.extend([c]*b)
  if len(a) > n*2:
    break

a.sort(reverse=True)
print(sum(a[:n]))
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

max_gcd = 0
for i in range(N):
  temp_A = A[:i] + A[i+1:]
  temp_gcd = temp_A[0]
  for j in range(N-1):
    temp_gcd = gcd(temp_gcd,temp_A[j])

  if temp_gcd > max_gcd:
    max_gcd = temp_gcd

print(max_gcd)

Fixed submission:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

L = [0]
R = [0]
for i in range(N-1):
  L.append(gcd(L[i],A[i]))
  R.append(gcd(R[i],A[-i-1]))

max_gcd = 0
for i in range(N):
  max_gcd = max(max_gcd, gcd(L[i],R[-i-1]))

print(max_gcd)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

comb = list(combinations(A,len(A)-1))
max_gcd = 0
for i in range(len(comb)):
  temp_gcd = comb[i][0]
  for j in range(1,len(comb[i])):
    temp_gcd = gcd(temp_gcd,comb[i][j])

  if temp_gcd > max_gcd:
    max_gcd = temp_gcd

print(max_gcd)

Fixed submission:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

L = [0]
R = [0]
for i in range(N-1):
  L.append(gcd(L[i],A[i]))
  R.append(gcd(R[i],A[-i-1]))

max_gcd = 0
for i in range(N):
  max_gcd = max(max_gcd, gcd(L[i],R[-i-1]))

print(max_gcd)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

comb = list(combinations(A,len(A)-1))
max_gcd = 0
for i in range(len(comb)):
  temp_gcd = comb[i][0]
  for j in range(1,len(comb[i])):
    temp_gcd = gcd(temp_gcd,comb[i][j])
    if temp_gcd < max_gcd:
      break
  max_gcd = max(max_gcd,temp_gcd)

print(max_gcd)

Fixed submission:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

L = [0]
R = [0]
for i in range(N-1):
  L.append(gcd(L[i],A[i]))
  R.append(gcd(R[i],A[-i-1]))

max_gcd = 0
for i in range(N):
  max_gcd = max(max_gcd, gcd(L[i],R[-i-1]))

print(max_gcd)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

comb = list(combinations(A,len(A)-1))
max_gcd = 0
for i in range(len(comb)):
  temp_gcd = comb[i][0]
  for j in range(1,len(comb[i])):
    temp_gcd = gcd(temp_gcd,comb[i][j])
  max_gcd = max(max_gcd,temp_gcd)

print(max_gcd)

Fixed submission:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

L = [0]
R = [0]
for i in range(N-1):
  L.append(gcd(L[i],A[i]))
  R.append(gcd(R[i],A[-i-1]))

max_gcd = 0
for i in range(N):
  max_gcd = max(max_gcd, gcd(L[i],R[-i-1]))

print(max_gcd)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
while '01' in s or '10' in s:
  s = s.replace('01','').replace('10','')
print(n-len(s))

Fixed submission:
s = list(input())
c0 = s.count('0')
c1 = s.count('1')
print(2*min(c1,c0))
Buggy python submission (verdict: Runtime Error):
from sys import setrecursionlimit

def find(parent, i):
  t = parent[i]
  if t < 0:
    return i
  t = find(parent, t)
  parent[i] = t
  return t

def unite(parent, i, j):
  i = find(parent, i)
  j = find(parent, j)
  if i == j:
    return
  parent[j] += parent[i]
  parent[i] = j

setrecursionlimit(10**6)

N, M = map(int, input().split())
AB = [[int(c) - 1 for c in input().split()] for _ in range(M)]

parent = [-1]*N
inconvenience = N*(N-1) // 2
result = []
for a, b in AB[::-1]:
  result.append(inconvenience)
  pa, pb = find(parent, a), find(parent, b)
  if pa != pb:
    inconvenience -= parent[pa] * parent[pb]
  unite(parent, a, b)

for i in range(N,-1,-1):
  print(result[i])

Fixed submission:
from sys import setrecursionlimit

def find(parent, i):
  t = parent[i]
  if t < 0:
    return i
  t = find(parent, t)
  parent[i] = t
  return t

def unite(parent, i, j):
  i = find(parent, i)
  j = find(parent, j)
  if i == j:
    return
  parent[j] += parent[i]
  parent[i] = j

setrecursionlimit(10**6)

N, M = map(int, input().split())
AB = [[int(c) - 1 for c in input().split()] for _ in range(M)]

parent = [-1]*N
inconvenience = N*(N-1) // 2
result = []
for a, b in AB[::-1]:
  result.append(inconvenience)
  pa, pb = find(parent, a), find(parent, b)
  if pa != pb:
    inconvenience -= parent[pa] * parent[pb]
  unite(parent, a, b)

for i in range(len(result)-1,-1,-1):
  print(result[i])
Buggy python submission (verdict: Runtime Error):
N, M = map(int,input().split())
if M == 1:
  print(0)
  exit()
X = list(map(int,input().split()))
X.sort()
dif = {}
for i in range(M-1):
  dif[i] = X[i+1]-X[i]
  
sorted_dif = sorted(dif.items(), key=lambda x:x[1], reverse=True)
difs = 0
for i in range(N-1):
  difs += sorted_dif[i][1]

print(X[-1]-X[0]-difs)

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

if N >= M:
  print(0)
  exit()
  
X = list(map(int,input().split()))
X.sort()

dif = {}
for i in range(M-1):
  dif[i] = X[i+1]-X[i]
  
sorted_dif = sorted(dif.items(), key=lambda x:x[1], reverse=True)
difs = 0
for i in range(N-1):
  difs += sorted_dif[i][1]

print(X[-1]-X[0]-difs)