Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N=int(input())
S=[*str(input())]

n=1
while N>n:
	n*=2

d=[[0]*(2*n) for _ in range(26)]

def ci(c):
	return "abcdefghijklmnopqrstuvwxyz".find(c)

def update(d,k,a):
	k+=n-1
	d[k]=a
	while k>0:
		k=~-k//2
		d[k]=d[k*2+1]+d[k*2+2]

def query(d,a,b,k,l,r):
	if r<=a or b<=l:
		return 0
	if a<=l and r<=b:
		return d[k]
	else:
		return query(d,a,b,k*2+1,l,(l+r)//2)+query(d,a,b,k*2+2,(l+r)//2,r)

for i,c in enumerate(S):
	update(d[ci(c)],i,1)

for i in range(int(input())):
	t,x,y=input().split()
	if t=='1':
		update(d[ci(S[int(x)-1])],int(x)-1,0)
		update(d[ci(y)],int(x)-1,1)
	else:
		a=0
		for j in range(26):
			if query(d[j],int(x)-1,int(y),0,0,n)>0:
				a+=1
		print(a)


Fixed submission:
import bisect

N=int(input())
S=list(str(input()))

def ci(x):
  return "abcdefghijklmnopqrstuvwxyz".find(x)

d=[[] for _ in range(26)]
for i,s in enumerate(S):
  d[ci(s)].append(i)

for i in range(int(input())):
  t,x,y=input().split()
  if t=="1":
    x=int(x)-1
    if S[x]!=y:
      l=bisect.bisect_left(d[ci(S[x])],x)
      d[ci(S[x])].pop(l)
      bisect.insort(d[ci(y)],x)
      S[x]=y
  else:
    x,y=int(x)-1,int(y)-1
    c=0
    for j in range(26):
      l=bisect.bisect_left(d[j],x)
      if l<len(d[j]) and d[j][l] <= y:
        c += 1
    print(c)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
input=sys.stdin.readline

def ci(c):
  return "abcdefghijklmnopqrstuvwxyz".find(c)

N=int(input())
S=[ci(c) for c in str(input())]+[0]
Q=int(input())

C=[[0]*26 for _ in range(N+1)]
for i in range(N):
  for j in range(26):
    C[i][j]=C[i-1][j]
  C[i][S[i]]+=1

L=list()

for i in range(Q):
  t,x,y=input().split()
  if t=='1':
    L.append([int(x)-1,ci(y)])
  else:
    t,l,r=0,int(x)-1,int(y)-1
    c=[0]*26
    for x,j in L:
      if l<=x and x<=r:
        c[j]+=1
        c[S[x]]-=1
    for j in range(26):
      if C[r][j]-C[l-1][j]+c[j]>0:
        t+=1
    print(t)


Fixed submission:
import bisect

N=int(input())
S=list(str(input()))

def ci(x):
  return "abcdefghijklmnopqrstuvwxyz".find(x)

d=[[] for _ in range(26)]
for i,s in enumerate(S):
  d[ci(s)].append(i)

for i in range(int(input())):
  t,x,y=input().split()
  if t=="1":
    x=int(x)-1
    if S[x]!=y:
      l=bisect.bisect_left(d[ci(S[x])],x)
      d[ci(S[x])].pop(l)
      bisect.insort(d[ci(y)],x)
      S[x]=y
  else:
    x,y=int(x)-1,int(y)-1
    c=0
    for j in range(26):
      l=bisect.bisect_left(d[j],x)
      if l<len(d[j]) and d[j][l] <= y:
        c += 1
    print(c)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
m=10**9+7

k=min(k,n-1)
c=[1]+[0]*k
h=[1]+[0]*k

for i in range(1,k+1):
  c[i]=c[i-1]*(n-i+1)* pow(i,m-2,m)
  h[i]=h[i-1]*(n-i)  * pow(i,m-2,m)

t=0
for i in range(k+1):
  t+=(c[i]*h[i])%m

print(t%m)


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

k=min(k,n-1)
t,c,h=1,1,1
for i in range(1,k+1):
  p=pow(i,m-2,m)
  c=(c*(n-i+1)* p)%m
  h=(h*(n-i)  * p)%m
  t=(t+c*h)%m

print(t%m)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
  N,D,A=map(int,input().split())
  m=sorted([int(j) for j in input().split()] for i in range(N))

  c,l=0,0
  while l<N:
    p=(m[l][1]+A-1)//A
    m[l][1],n,r,c=0,0,l+1,c+p
    while r<N and m[l][0]+2*D>=m[r][0]:
      if m[r][1]>A*p:
        m[r][1]-=A*p
        if n==0:
          n=r
      elif m[r][1]!=0:
        m[r][1]=0
      r+=1
    else:
      l=n if n!=0 else r

  print(c)

main()


Fixed submission:
import bisect

def main():
  N,D,A=map(int,input().split())
  m=sorted([int(j) for j in input().split()] for i in range(N))

  x=[m[i][0] for i in range(N)]
  es=[0]*(N+1)
  a,c=0,0
  for i in range(N):
    c-=es[i]
    if m[i][1]>A*c:
      t=(m[i][1]-A*c+A-1)//A
      a+=t
      c+=t
      es[bisect.bisect_right(x,x[i]+2*D)]+=t
  print(a)

main()

Buggy python submission (verdict: Time Limit Exceeded):
N,D,A=map(int,input().split())
m=sorted([int(j) for j in input().split()] for i in range(N))

def main():
  c,l=0,0
  while l<N:
    p=(m[l][1]+A-1)//A
    m[l][1],n,r,c=0,0,l+1,c+p
    while r<N and m[l][0]+2*D>=m[r][0]:
      if m[r][1]>A*p:
        m[r][1]-=A*p
        if n==0:
          n=r
      elif m[r][1]!=0:
        m[r][1]=0
      r+=1
    else:
      l=n if n!=0 else r

  print(c)

main()


Fixed submission:
import bisect

def main():
  N,D,A=map(int,input().split())
  m=sorted([int(j) for j in input().split()] for i in range(N))

  x=[m[i][0] for i in range(N)]
  es=[0]*(N+1)
  a,c=0,0
  for i in range(N):
    c-=es[i]
    if m[i][1]>A*c:
      t=(m[i][1]-A*c+A-1)//A
      a+=t
      c+=t
      es[bisect.bisect_right(x,x[i]+2*D)]+=t
  print(a)

main()

Buggy python submission (verdict: Time Limit Exceeded):
N,D,A=map(int,input().split())
m=sorted([int(j) for j in input().split()] for i in range(N))

def main():
  c,l=0,0
  while l<N:
    p=(m[l][1]+A-1)//A
    m[l][1],n,r,c=0,0,l+1,c+p
    while r<N and m[l][0]+2*D>=m[r][0]:
      if m[r][1]>A*p:
        m[r][1]-=A*p
        if n==0:
          n=r
      else:
        m[r][1]=0
      r+=1
    else:
      l=n if n!=0 else r

  print(c)

main()


Fixed submission:
import bisect

def main():
  N,D,A=map(int,input().split())
  m=sorted([int(j) for j in input().split()] for i in range(N))

  x=[m[i][0] for i in range(N)]
  es=[0]*(N+1)
  a,c=0,0
  for i in range(N):
    c-=es[i]
    if m[i][1]>A*c:
      t=(m[i][1]-A*c+A-1)//A
      a+=t
      c+=t
      es[bisect.bisect_right(x,x[i]+2*D)]+=t
  print(a)

main()
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(x) for x in input().split()]
S=[0]*60

for a in A:
  c=0
  while a>0:
    if a&1!=0:
      S[c]+=1
    a>>=1
    c+=1

s,c=0,0
while c<60:
  s+=S[c]*(N-S[c])*((2**c)%(10**9+7))
  c+=1

print(s%(10**9+7))


Fixed submission:
N=int(input())
A=[int(x) for x in input().split()]

s=0
for c in range(60):
  m=1<<c
  bc=len([1 for x in A if x&m])
  s+=bc*(N-bc)*m
  s%=10**9+7
  
print(s)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(x) for x in input().split()]
S=[0]*60

for i,a in enumerate(A):
  c=0
  while a>0:
    if a&1!=0:
      S[c]+=1
    a>>=1
    c+=1

s,c=0,0
while c<60:
  s+=S[c]*(N-S[c])*((2**c)%(10**9+7))
  c+=1

print(s%(10**9+7))


Fixed submission:
N=int(input())
A=[int(x) for x in input().split()]

s=0
for c in range(60):
  m=1<<c
  bc=len([1 for x in A if x&m])
  s+=bc*(N-bc)*m
  s%=10**9+7
  
print(s)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(x) for x in input().split()]
S=[[0]*60 for x in range(N+1)]

for i,a in enumerate(A):
  c=0
  while a>0:
    if a&1!=0:
      S[i+1][c]=1
    a>>=1
    c+=1
  for c in range(60):
    S[i+1][c]+=S[i][c]

s=0
for i,a in enumerate(A[:N-1]):
  c,i=0,i+1
  while c<60:
    s+=2**c*((S[N][c]-S[i][c]) if a&1==0 else (N-S[N][c]+S[i][c]-i))
    s%=10**9+7
    a>>=1
    c+=1

print(s)


Fixed submission:
N=int(input())
A=[int(x) for x in input().split()]

s=0
for c in range(60):
  m=1<<c
  bc=len([1 for x in A if x&m])
  s+=bc*(N-bc)*m
  s%=10**9+7
  
print(s)
Buggy python submission (verdict: Runtime Error):
N=int(input())
v=[[] for i in range(N)]
r=list()

def wps(s,d,u):
  c=1
  for i in range(len(v[d])):
    if v[d][i][0]!=s:
      c=c if u!=c else c+1
      v[d][i][1]=c
      wps(d,v[d][i][0],c)
      c+=1
    else:
      v[d][i][1]=u


for i in range(N-1):
  a,b=map(int,input().split())
  v[a-1].append([b-1,0,i])
  v[b-1].append([a-1,0,i])

wps(-1,0,-1)

m=0
for i in range(N):
  for j in range(len(v[i])):
    if i<v[i][j][0]:
      r.append(v[i][j])
  m=max(m,len(v[i]))

print(m)
r.sort(key=lambda x:x[2])
for e in r:
	print(e[1])


Fixed submission:
import sys
sys.setrecursionlimit(10**5)

N=int(input())
v=[[] for i in range(N)]
r=list()

def wps(s,d,u):
  c=1
  for i in range(len(v[d])):
    if v[d][i][0]!=s:
      c=c if u!=c else c+1
      v[d][i][1]=c
      wps(d,v[d][i][0],c)
      c+=1
    else:
      v[d][i][1]=u


for i in range(N-1):
  a,b=map(int,input().split())
  v[a-1].append([b-1,0,i])
  v[b-1].append([a-1,0,i])

wps(-1,0,-1)

m=0
for i in range(N):
  for j in range(len(v[i])):
    if i<v[i][j][0]:
      r.append(v[i][j])
  m=max(m,len(v[i]))

print(m)
r.sort(key=lambda x:x[2])
for e in r:
	print(e[1])
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
f=[int(x) for x in input().split()]

a.sort()
f.sort(reverse=True)

l,u=-1,f[0]*a[-1]
while l+1<u:
  m=(l+u)//2
  s=0
  for i in range(n):
    s+= a[i]-m//f[i] if a[i]>m//f[i] else 0
  if s<=k:
    u=m
  else:
    l=m

print(u)

Fixed submission:
import numpy as np

n,k=map(int,input().split())
a=[int(x) for x in input().split()]
f=[int(x) for x in input().split()]

a.sort()
f.sort(reverse=True)

A=np.array(a)
F=np.array(f)
S=sum(a)

l,u=-1,f[0]*a[-1]
while l+1<u:
  m=(l+u)//2
  s=0
  if S-np.minimum(A,m//F).sum()<=k:
    u=m
  else:
    l=m

print(u)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n=int(input())
l=[int(x) for x in input().split()]

l.sort()

t=0
for i in range(n):
  for j in range(i+1,n):
    a = max(j+1, bisect.bisect_left(l,l[j]-l[i]))
    b = bisect.bisect_left(l,l[i]+l[j])
    t += b-a if b>a else 0

print(t)


Fixed submission:
import bisect

n=int(input())
l=sorted(map(int,input().split()))

t=0
for i in range(n):
  for j in range(i+1,n):
    a = j+1
    b = bisect.bisect_left(l,l[i]+l[j])
    t += b-a if b>a else 0

print(t)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l=[int(x) for x in input().split()]

c=0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if l[i] < l[j]+l[k] and l[j] < l[i]+l[k] and l[k] < l[i]+l[j]:
        c += 1

print(c)


Fixed submission:
import bisect

n=int(input())
l=sorted(map(int,input().split()))

t=0
for i in range(n):
  for j in range(i+1,n):
    a = j+1
    b = bisect.bisect_left(l,l[i]+l[j])
    t += b-a if b>a else 0

print(t)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
S=input()
a=[0 for x in range(len(S))]

def zal(s):
  a[0]=len(s)
  i,j=1,0
  while i < a[0]:
    while i+j < a[0] and s[j]==s[i+j]:
      j+=1
    a[i]=j
    if j==0:
      i+=1
    else:
      k=1
      while i+k < a[0] and k+a[k] < j:
        a[i+k]=a[k]
        k+=1
      i+=k
      j-=k
  m=0
  for i in range(1,a[0]):
    if i >= a[i]:
      m=max(m,a[i])
  return m

m,i=0,0
while i < len(S)-1:
  m = max(m,zal(S[i:]))
  i += 1

print(m)


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

m,j = 0,0
for i in range(n):
  if s[j:i+1] in s[i+1:]:
    m=i-j+1
  else:
    j+= 1

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

ls=len(s)
lt=len(t)

for i in range(lt):
  if (t[i] in s) == False:
    print(-1)
    exit()

si,ti=0,0
while ti < lt:
  if s[si%ls]==t[ti]:
    ti += 1
  si += 1
print(si)


Fixed submission:
import bisect

s=input()
t=input()

sl=len(s)
tl=len(t)

r="abcdefghijklmnopqrstuvwxyz"
p=[[] for i in range(26)]

for i in range(sl):
  p[r.find(s[i])].append(i)

for i in range(26):
  if len(p[i])>0:
    p[i].append(p[i][0]+sl)

s=set()
for i in range(tl):
  s.add(t[i])
for c in s:
  if len(p[r.find(c)]) == 0:
     print(-1)
     exit()

ti, si = 0, -1
while ti < tl:
  si +=  p[r.find(t[ti])][bisect.bisect_right(p[r.find(t[ti])], si%sl)] - si%sl
  ti += 1

print(si+1)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
l=[[] for i in range(m)]
s=[]
for i in range(n):
   a,b=map(int,input().split())
   if a<=m:
     l[a-1].append(b)

t=0
for i in range(m):
   s += l[i]
   if len(s)>0:
      s.sort(reverse=True)
      t+=s.pop(0)

print(t)


Fixed submission:
import heapq

n,m=map(int,input().split())
l=[[] for i in range(m)]
s=[]
for i in range(n):
   a,b=map(int,input().split())
   if a<=m:
     l[a-1].append(b)

t=0
heapq.heapify(s)

for i in range(m):
  for j in range(len(l[i])):
    heapq.heappush(s,-l[i][j])
  if len(s)>0:
    t-=heapq.heappop(s)

print(t)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(x) for x in input().split()]

S = 0
for i in range(N):
   S += A[i]

for i in range(N):
  X = 0
  for j in range(N):
    if j % 2:
       X += A[(i+j)%N]
  print(S-2*X, end=" ")
print()


Fixed submission:
N = int(input())
A = [int(x) for x in input().split()]

S = 0
for i in range(N):
  S += A[i]
X = S
for i in range(N):
  if i%2:
    X -= 2*A[i]
print(X, end=" ")
for i in range(1,N):
    X = 2*A[i-1]-X
    print(X, end=" ")
print()
Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10000)

def dps(u,p,c):
  x[c]= u
  u = k-(1 if p<0 else 2)
  for i in range(len(l[c])):
    if l[c][i]!=p:
      if u>0:
        dps(u,c,l[c][i])
        u-=1
      else:
        break
  return

n,k=map(int,input().split())

l=[[] for i in range(n)]
x=[0]*n

for i in range(n-1):
  a,b= map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

dps(k,-1,0)

t=1
for i in range(n):
  t=(t*x[i])%(10**9+7)

print(t)


Fixed submission:
import sys

sys.setrecursionlimit(100000)

def dps(u,p,c):
  x[c]= u
  u = k-(1 if p<0 else 2)
  for i in range(len(l[c])):
    if l[c][i]!=p:
      if u>0:
        dps(u,c,l[c][i])
        u-=1
      else:
        break
  return

n,k=map(int,input().split())

l=[[] for i in range(n)]
x=[0]*n

for i in range(n-1):
  a,b= map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

dps(k,-1,0)

t=1
for i in range(n):
  t=(t*x[i])%(10**9+7)

print(t)

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

sys.getrecursionlimit(10000)

def dps(u,p,c):
  x[c]= u
  u = k-(1 if p<0 else 2)
  for i in range(len(l[c])):
    if l[c][i]!=p:
      if u>0:
        dps(u,c,l[c][i])
        u-=1
      else:
        break
  return

n,k=map(int,input().split())

l=[[] for i in range(n)]
x=[0]*n

for i in range(n-1):
  a,b= map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

dps(k,-1,0)

t=1
for i in range(n):
  t=(t*x[i])%(10**9+7)

print(t)


Fixed submission:
import sys

sys.setrecursionlimit(100000)

def dps(u,p,c):
  x[c]= u
  u = k-(1 if p<0 else 2)
  for i in range(len(l[c])):
    if l[c][i]!=p:
      if u>0:
        dps(u,c,l[c][i])
        u-=1
      else:
        break
  return

n,k=map(int,input().split())

l=[[] for i in range(n)]
x=[0]*n

for i in range(n-1):
  a,b= map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

dps(k,-1,0)

t=1
for i in range(n):
  t=(t*x[i])%(10**9+7)

print(t)

Buggy python submission (verdict: Runtime Error):
def dps(u,p,c):
  x[c]= u
  u = k-(1 if p<0 else 2)
  for i in range(len(l[c])):
    if l[c][i]!=p:
      if u>0:
        dps(u,c,l[c][i])
        u-=1
      else:
        break
  return

n,k=map(int,input().split())

l=[[] for i in range(n)]
x=[0]*n

for i in range(n-1):
  a,b= map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

dps(k,-1,0)

t=1
for i in range(n):
  t=(t*x[i])%(10**9+7)

print(t)


Fixed submission:
import sys

sys.setrecursionlimit(100000)

def dps(u,p,c):
  x[c]= u
  u = k-(1 if p<0 else 2)
  for i in range(len(l[c])):
    if l[c][i]!=p:
      if u>0:
        dps(u,c,l[c][i])
        u-=1
      else:
        break
  return

n,k=map(int,input().split())

l=[[] for i in range(n)]
x=[0]*n

for i in range(n-1):
  a,b= map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

dps(k,-1,0)

t=1
for i in range(n):
  t=(t*x[i])%(10**9+7)

print(t)
Buggy python submission (verdict: Time Limit Exceeded):
MASK=10**9+7
N,K=map(int,input().split())

def cmb(n,r):
  t=1
  for i in range(r):
    t *= n-i
  for i in range(r,1,-1):
    t //= i
  return t

for i in range(0,K):
  print((cmb(N+1-K,i+1)*cmb(K-1,i))%MASK)


Fixed submission:
MASK=10**9+7
N,K=map(int,input().split())

F=[1]*(N+1)
for i in range(1,N+1):
  F[i] = i* F[i-1]

def cmb(n,r):
  return F[n]//F[r]//F[n-r]

for i in range(0,K):
  print((cmb(N+1-K,i+1)*cmb(K-1,i))%MASK)
Buggy python submission (verdict: Runtime Error):
N,X=map(int,input().split())
L=[int(x) for x in input().split()]

C=D=0
while C<X:
  D+=L[C]
  if D>X:
    break;
  C+=1
print(C+1)


Fixed submission:
N,X=map(int,input().split())
L=[int(x) for x in input().split()]

C=D=0
while C<N:
  D+=L[C]
  if D>X:
    break;
  C+=1
print(C+1)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
a = [int(input()) for i in range(M)] 
t = d = [0]*(N+1)

for i in range(M):
  d[a[i]] = 1

t[0]=1
t[1]=0 if a[0]==1 else 1
for i in range(2,N+1):
  t[i] = 0 if d[i] else t[i-1]+t[i-2]
print (t[N] % 1000000007)


Fixed submission:
N,M = map(int,input().split())
a = [int(input()) for i in range(M)] 
t = d = [0]*(N+1)

for i in range(M):
  d[a[i]] = 1

t[0]=t[1]=1
if M>0:
  t[1] = 0 if (a[0]==1) else 1

for i in range(2,N+1):
  t[i] = 0 if d[i] else t[i-1]+t[i-2]
print (t[N] % 1000000007)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[int(i) for i in input().split()]

a.sort()
for i in range(m):
 b,c=map(int,input().split())
 for i in range(b):
  if a[i] < c:
   a[i] = c
  else:
   break
 for j in range(i+1):
  if a[j] > a[j+i+1]:
   a[j],a[j+i+1]=a[j+i+1],a[j]
  else:
   break

print(sum(a))

Fixed submission:
n,m=map(int,input().split())
l=[[int(x),1] for x in input().split()]
for i in range(m):
  b,c=map(int,input().split())
  l.append([c,b])

s = sorted(l, key=lambda x:x[0], reverse=True)

c=n
t=0
i=0
while c>0:
  n = s[i][1] if c>=s[i][1] else c
  t += s[i][0] * n
  c -= n
  i += 1

print(t)

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=[int(i) for i in input().split()]

for i in range(m):
 a.sort()
 b,c=map(int, input().split())
 for i in range(b):
  if a[i] < c:
   a[i] = c
  else:
   break
print(sum(a))

Fixed submission:
n,m=map(int,input().split())
l=[[int(x),1] for x in input().split()]
for i in range(m):
  b,c=map(int,input().split())
  l.append([c,b])

s = sorted(l, key=lambda x:x[0], reverse=True)

c=n
t=0
i=0
while c>0:
  n = s[i][1] if c>=s[i][1] else c
  t += s[i][0] * n
  c -= n
  i += 1

print(t)

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[int(i) for i in input().split()]

for i in range(m):
 a.sort()
 print(a)
 b,c=map(int, input().split())
 for i in range(b):
  if a[i] < c:
   a[i] = c
  else:
   break
print(sum(a))


Fixed submission:
n,m=map(int,input().split())
l=[[int(x),1] for x in input().split()]
for i in range(m):
  b,c=map(int,input().split())
  l.append([c,b])

s = sorted(l, key=lambda x:x[0], reverse=True)

c=n
t=0
i=0
while c>0:
  n = s[i][1] if c>=s[i][1] else c
  t += s[i][0] * n
  c -= n
  i += 1

print(t)
Buggy python submission (verdict: Runtime Error):
n = int(input())

ulist = []

for _ in range(n+1):
    ulist.append([])

vlist = [False]*(n+1)

for _ in range(1,n):
    u, v, w = map(int, input().split())
    ulist[u].append([v,w])
    ulist[v].append([u,w])

def check(checkV, fromV):
    for data in ulist[checkV]:
        if data[0] != fromV:
            vlist[data[0]] = vlist[checkV] if data[1] % 2 == 0 else not vlist[checkV]
            check(data[0], checkV)

check(1, 0)

for i in range(1,n+1):
    print(1 if vlist[i] else 0)


Fixed submission:
import sys

sys.setrecursionlimit(1000000)

n = int(input())

ulist = []

for _ in range(n+1):
    ulist.append([])

vlist = [False]*(n+1)

for _ in range(1,n):
    u, v, w = map(int, input().split())
    ulist[u].append([v,w])
    ulist[v].append([u,w])

def check(checkV, fromV):
    for data in ulist[checkV]:
        if data[0] != fromV:
            vlist[data[0]] = vlist[checkV] if data[1] % 2 == 0 else not vlist[checkV]
            check(data[0], checkV)

check(1, 0)

for i in range(1,n+1):
    print(1 if vlist[i] else 0)
Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

n=int(input())
al=input().split()
al_i = [int(s) for s in al]

if (n == 2):
   print(gcd(al_i[0],al_i[1]))
   return

fg = [0] * n
bg = [0] * n

for x in range(n):
   if (x == 0):
       fg[0] = al_i[0]
       y = 1
   else:
      while y <= x:
         fg[y] = gcd(fg[y-1], al_i[y])
         y += 1

for x in range(n):
   if (x == 0):
      bg[0] = al_i[n-1]
      y = 1
   else:
      while y <= x:
         bg[y] = gcd(bg[y-1], al_i[n-1-y])
         y += 1

m = 0
gm = 0

for x in range(n):
   if (x == 0):
      g = bg[n-2]
   elif (x == n):
      g = fg[n-2]
   else:
      g = gcd(fg[x-1],bg[n-2-x])
   if (g > gm):
      gm = g

print(gm)


Fixed submission:
a,b,t=(int(x) for x in input().split())
print(int((t+0.5)/a)*b)

Buggy python submission (verdict: Runtime Error):
import fractions
from functools import reduce

def gcd(*numbers):
   return reduce(fractions.gcd, numbers)

n=int(input())
al=input().split()
al_i = [int(s) for s in al]
m = max(al_i)
gm = 0

for x in range(n):
   t = al_i[x]
   al_i[x] = m
   g = gcd(*al_i)
   al_i[x] = t
   if g>gm:
      gm = g
print(gm)


Fixed submission:
a,b,t=(int(x) for x in input().split())
print(int((t+0.5)/a)*b)
Buggy python submission (verdict: Runtime Error):
N,Q=map(int,input().split())
S=input()
c=[0]
t = 0
for i in range(1,N):
    t += 1 if  S[i-1:i+1]=='AC' else 0
    c.append(t)
for _ in range(Q):
    l,r=map(int, intput().split))
    print(c[r]-c[l])


Fixed submission:
N,Q=[int(i) for i in input().split()]
S=input()

c=[0]
t = 0
for i in range(1,N):
   t += 1 if  (S[i-1]=='A' and S[i] == 'C') else 0
   c.append(t)

for _ in range(Q):
    l,r=[int(x)-1 for x in input().split()]
    print(c[r]-c[l])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q=[int(x) for x in input().split()]
S=input()
l=r=0
for _ in range(Q):
    l,r=[int(x) for x in input().split()]
    t=0
    for i in range(l-1,r-1):
        t += 1 if S[i]=='A' and S[i+1]=='C' else 0
    print(t)


Fixed submission:
N,Q=[int(i) for i in input().split()]
S=input()

c=[0]
t = 0
for i in range(1,N):
   t += 1 if  (S[i-1]=='A' and S[i] == 'C') else 0
   c.append(t)

for _ in range(Q):
    l,r=[int(x)-1 for x in input().split()]
    print(c[r]-c[l])
Buggy python submission (verdict: Runtime Error):
a,b,q=map(int, input().split())

s=[-2*10**10]+[int(input()) for _ in range(a)]+[2*10**10]
t=[-2*10**10]+[int(input()) for _ in range(b)]+[2*10**10]
x=[int(input()) for _ in range(q)]

for i in range(q):
  j = bisect.bisect_left(s,x[i])
  al = x[i] - s[j-1]
  ar = s[j] - x[i]
  j = bisect.bisect_left(t,x[i])
  bl = x[i] - t[j-1]
  br = t[j] - x[i]
  l = min(max(al, bl), max(ar, br), 2*al+br, 2*ar+bl, 2*bl+ar, 2*br+al)
  print(l)


Fixed submission:
import bisect

a,b,q=map(int, input().split())

s=[-2*10**10]+[int(input()) for _ in range(a)]+[2*10**10]
t=[-2*10**10]+[int(input()) for _ in range(b)]+[2*10**10]
x=[int(input()) for _ in range(q)]

for i in range(q):
  j = bisect.bisect_left(s,x[i])
  al = x[i] - s[j-1]
  ar = s[j] - x[i]
  j = bisect.bisect_left(t,x[i])
  bl = x[i] - t[j-1]
  br = t[j] - x[i]
  l = min(max(al, bl), max(ar, br), 2*al+br, 2*ar+bl, 2*bl+ar, 2*br+al)
  print(l)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
l=[[] for _ in range(n)]
d=list()

for i in range(m):
  p,q=map(int,input().split())
  l[p-1].append(q)
  d.append([p,q])
 
for i in range(n):
  if len(l[i])>0:
    l[i].sort()

for i in range(m):
  print(str(d[i][0]).zfill(6)+str(l[d[i][0]-1].index(d[i][1])+1).zfill(6))


Fixed submission:
import bisect

n,m=map(int,input().split())
l=[[] for _ in range(n)]
d=list()

for i in range(m):
  p,q=map(int,input().split())
  l[p-1].append(q)
  d.append([p-1,q])
 
for i in range(n):
  if len(l[i])>0:
    l[i].sort()

for i in range(m):
  o = bisect.bisect_left(l[d[i][0]], d[i][1])+1
  print(str(d[i][0]+1).zfill(6)+str(o).zfill(6))