Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
a=[]
b=[]
s=[0]


for i in range(0,n-1):
    A,B=map(int,input().split())
    a.append(A)
    b.append(B)
    s.append(0)
for i in range(0,q):
    P,X=map(int,input().split())
    s[P-1]=s[P-1]+X


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

print(' '.join(map(str,s)))










Fixed submission:
from operator import itemgetter
n,q=map(int,input().split())
a=[]
s=[0]


for i in range(n-1):
    a.append([int(j) for j in input().split()])
    s.append(0)

a.sort(key=itemgetter(0))

for i in range(0,q):
    P,X=map(int,input().split())
    s[P-1]=s[P-1]+X


for j in range(0,n-1):
    s[a[j][1]-1]=s[a[j][1]-1]+s[a[j][0]-1]


print(' '.join(map(str,s)))

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
a=[]
b=[]
p=[]
x=[]
s=[0]


for i in range(0,n-1):
    A,B=map(int,input().split())
    a.append(A)
    b.append(B)
    s.append(0)
for i in range(0,q):
    P,X=map(int,input().split())
    p.append(P)
    x.append(X)
    s[P-1]=s[P-1]+X


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

print(' '.join(map(str,s)))

Fixed submission:
from operator import itemgetter
n,q=map(int,input().split())
a=[]
s=[0]


for i in range(n-1):
    a.append([int(j) for j in input().split()])
    s.append(0)

a.sort(key=itemgetter(0))

for i in range(0,q):
    P,X=map(int,input().split())
    s[P-1]=s[P-1]+X


for j in range(0,n-1):
    s[a[j][1]-1]=s[a[j][1]-1]+s[a[j][0]-1]


print(' '.join(map(str,s)))
Buggy python submission (verdict: Runtime Error):
a,b=int(input())

c1=a+b
c2=a-b
c3=a*b

if c1>=c2 and c1>=c3:
    print(c1)

elif c2>=c1 and c2>=c3:
    print(c2)
else:
    print(c3)



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


c1=a+b
c2=a-b
c3=a*b

if c1>=c2 and c1>=c3:
    print(c1)

elif c2>=c1 and c2>=c3:
    print(c2)
else:
    print(c3)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=[]
z=0

for i in range(0,n):
    m=input()
    y=list(m)
    y.sort()
    m=''.join(y)
    s.append(m)



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


z=(z-n)//2

print(z)

Fixed submission:
n=int(input())
s=[]
z=0
d=0

for i in range(0,n):
    m=input()
    y=list(m)
    y.sort()
    m=''.join(y)
    s.append(m)

s.sort()

for j in range(0,n-1):
    if s[j]==s[j+1]:
        d=d+1
    else:
        if d==0:
            continue
        else:
            f=d*(d+1)//2
            z=z+f
            d=0
if d!=0:
    f=d*(d+1)//2
    z=z+f

print(z)
Buggy python submission (verdict: Runtime Error):
s=int(input())
S=list(s)
a=0

for i in range(0,3):
    if S[i]==S[i+1]:
        print('Bad')
        break
    else:
        a=a+1

if a==3:
    print('Good')

Fixed submission:
s=input()
S=list(s)
a=0

for i in range(0,3):
    if S[i]==S[i+1]:
        print('Bad')
        break
    else:
        a=a+1

if a==3:
    print('Good')
Buggy python submission (verdict: Runtime Error):
x,a=map(int,input(),split())
if x<A:
    print('0')

else:
    print('10')

Fixed submission:
x,a=map(int,input().split())
if x<a:
    print(0)

else:
    print(10)
Buggy python submission (verdict: Runtime Error):
w,h,x,y=map(int,input().split())




elif x==w/2 and y==h/2:
    s=1
else:
    s=0


S=w*h/2

print(str(S)+' '+str(s))

Fixed submission:
w,h,x,y=map(int,input().split())

if w==h and x==y and x==w/2:
    s=1


elif x==w/2 and y==h/2:
    s=1
else:
    s=0


S=w*h/2

print(str(S)+' '+str(s))
Buggy python submission (verdict: Runtime Error):
import collections

#文字列を一文字ずつ取得したいとき
def inputStrOnebyOne():
    s = list(input())
    return s

#整数を一つずつリストに入れる
def inputOnebyOne_Int():
    a = list(int(x) for x in input().split())
    return a

def main():
    a,b = input().split()
    c,d = input().split("-")
    if a == str(len(c)) and b == str(len(d)):
        print("Yes")
    else:
        print("No")

if __name__=='__main__':
    main()

Fixed submission:
import collections

#文字列を一文字ずつ取得したいとき
def inputStrOnebyOne():
    s = list(input())
    return s

#整数を一つずつリストに入れる
def inputOnebyOne_Int():
    a = list(int(x) for x in input().split())
    return a

def main():
    a,b = input().split()
    s = input()
    if s.count("-") == 1:
        c,d = s.split("-")
        if a == str(len(c)) and b == str(len(d)):
            print("Yes")
        else:
            print("No")
    else:
        print("No")

if __name__=='__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
	total = input()
	a = list(int(x) for x in input().split())
	a.sort()
	cntItem = 0
	cntRem = 0
	i = 0

	while i < int(total):
		cntItem = a.count(a[i])
		if a[i] < cntItem:
			cntRem+= cntItem - a[i]
		elif a[i] > cntItem:
			cntRem+= cntItem
		i+= cntItem
    
	print(cntRem)


if __name__=='__main__':
    main()

Fixed submission:
import collections

#文字列を一文字ずつ取得したいとき
def inputStrOnebyOne():
    s = list(input())
    return s

#整数を一つずつリストに入れる
def inputOnebyOne_Int():
    a = list(int(x) for x in input().split())
    return a

def main():
	n = input()
	a = list(map(int,input().split()))
	c = collections.Counter(a)
	cntRem = 0

	for key, val in c.items():
		if key < val:
			cntRem+= val - key
		elif key > val:
			cntRem+= val
	print(cntRem)

if __name__=='__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import collections

#文字列を一文字ずつ取得したいとき
def inputStrOnebyOne():
    s = list(input())
    return s

#整数を一つずつリストに入れる
def inputOnebyOne_Int():
    a = list(int(x) for x in input().split())
    return a

def main():
    s = inputStrOnebyOne()
    ret = []
    for i in range(len(s)):
        if s[i] == "0":
            ret.append(s[i])
        elif s[i] == "1":
            ret.append(s[i])
        else:
            ret.pop()
    print(''.join(ret))

if __name__=='__main__':
    main()

Fixed submission:
import collections

#文字列を一文字ずつ取得したいとき
def inputStrOnebyOne():
    s = list(input())
    return s

#整数を一つずつリストに入れる
def inputOnebyOne_Int():
    a = list(int(x) for x in input().split())
    return a

def main():
    s = inputStrOnebyOne()
    ret = []
    for i in range(len(s)):
        if s[i] == "0":
            ret.append(s[i])
        elif s[i] == "1":
            ret.append(s[i])
        else:
            if 1<=len(ret):
                ret.pop()
    print(''.join(ret))

if __name__=='__main__':
    main()
Buggy python submission (verdict: Runtime Error):
n = int(input())

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

if(len(a) >2):
  result = sum(b) + sum(c) - c[a[-1]-1]
  print(result)
else:
  result = sum(b) + c[0]
  print(result)


Fixed submission:
n = int(input())

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

before = -100
result = sum(b)

for i in a:
  if(i == before+1):
    result += c[before-1]
  before = i
  
print(result)
Buggy python submission (verdict: Runtime Error):
n = int(input())
H = [int(h) for h in input().split()]

result = []
count = 0
for i in range(n-1):
  if (H[i]>=H[i+1]):
    count+=1
    if(i == n-2):
      result.append(count)
  else:
    result.append(count)
    count=0
    
print(max(result))

Fixed submission:
n = int(input())
H = [int(h) for h in input().split()]

result = []
count = 0
if(n==1):
  print(0)
  exit()

for i in range(n-1):
  if (H[i]>=H[i+1]):
    count+=1
    if(i == n-2):
      result.append(count)
  else:
    result.append(count)
    count=0
    
print(max(result))
Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int,input().split())

A = [[]]*(H*W+1)
for i in range(H):
  a = list(map(int,input().split()))
  for j in range(W):
    A[a[j]] = [i, j]

Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]

def magic(LR):
  magic = 0
  for i in range(int((LR[1]-LR[0])/D)):
    magicx = abs(A[LR[0]+i*D][0] - A[LR[0]+(i+1)*D][0]) 
    magicy = abs(A[LR[0]+i*D][1] - A[LR[0]+(i+1)*D][1]) 
    magic += magicx + magicy
  return magic

for i in range(Q):
  if (LR[i][0] == LR[i][1]):
    print(0)
  else:
    print(magic(LR[i]))


Fixed submission:
H, W, D = map(int,input().split())

A = [[]]*(H*W+1)
for i in range(H):
  a = list(map(int,input().split()))
  for j in range(W):
    A[a[j]] = [i, j]

Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]

def magic(LR):
  magic = 0
  x = LR[0]
  y = LR[1]
  magicx = abs(A[x][0] - A[y][0]) 
  magicy = abs(A[x][1] - A[y][1]) 
  return magicx + magicy

magiclist = [0]*(H*W+1)
for i in range(D+1,H*W+1):
  magiclist[i] = magiclist[i-D] + magic([i-D,i])

for i in range(Q):
  x = LR[i][0]
  y = LR[i][1]
  if (x == y):
    print(0)
  else:
    print(magiclist[y]- magiclist[x])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]

def find(n):
  for i in range(len(A)):
    if n in A[i]:
      return [i, A[i].index(n)]

def magic(LR):
  magic = 0
  for i in range(int((LR[1]-LR[0])/D)):
    start = find(LR[0]+i*D)
    goal = find((LR[0]+(i+1)*D))
    magic += (abs(start[0]-goal[0]) + abs(start[1]-goal[1]))
  return magic
  
for i in range(len(LR)):
  if (LR[i][0] == LR[i][1]):
    print(0)
  else:
    print(magic(LR[i]))


Fixed submission:
H, W, D = map(int,input().split())

A = [[]]*(H*W+1)
for i in range(H):
  a = list(map(int,input().split()))
  for j in range(W):
    A[a[j]] = [i, j]

Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]

def magic(LR):
  magic = 0
  x = LR[0]
  y = LR[1]
  magicx = abs(A[x][0] - A[y][0]) 
  magicy = abs(A[x][1] - A[y][1]) 
  return magicx + magicy

magiclist = [0]*(H*W+1)
for i in range(D+1,H*W+1):
  magiclist[i] = magiclist[i-D] + magic([i-D,i])

for i in range(Q):
  x = LR[i][0]
  y = LR[i][1]
  if (x == y):
    print(0)
  else:
    print(magiclist[y]- magiclist[x])
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys;
import string;
sys.setrecursionlimit(20000) # 再起呼び出しの最大数をセット

import copy
import itertools

from functools import lru_cache
#@lru_cache(maxsize = None)

PPP = 1000000007

# 整数の入力
#n = int(input())

# スペース区切りの整数の入力
#a = [int(x) for x in input().split()]
a, b, c, d = map(int, input().split())
#print("sp", n, k, file=sys.stderr)
#p, q, r = map(int, input().split())
#s = [int(x) for x in input().split()]
#t = [int(x) for x in input().split()]

# 改行区切りの整数の入力
#a = []
#for x in range(n):
#  a.append(int(input()))
#  a.append([int(x) for x in input().split()])
#p = [int(x) for x in input().split()]
#a.sort()
#print(l, file=sys.stderr)

# 文字列の入力
#s = input()

# 出力
#print("{} {}".format(a+b+c, s))
#a.sort()
#print(set(a), file=sys.stderr)
#print(len(set(a)))

#cache = dict()

import re

def doit():
  res = 0
  for x in range(a, b + 1):
    if x % c == 0:
      continue
    if x % d == 0:
      continue
    res += 1
  return res

#print(doit([0] * 4))
#doit(s)
#print(doit())
try:
  print(doit())
except Exception as e:
  print("e", e, file=sys.stderr)


Fixed submission:
# -*- coding: utf-8 -*-
import sys;
import string;
sys.setrecursionlimit(20000) # 再起呼び出しの最大数をセット

import copy
import itertools

from functools import lru_cache
#@lru_cache(maxsize = None)

PPP = 1000000007

# 整数の入力
#n = int(input())

# スペース区切りの整数の入力
#a = [int(x) for x in input().split()]
a, b, c, d = map(int, input().split())
#print("sp", n, k, file=sys.stderr)
#p, q, r = map(int, input().split())
#s = [int(x) for x in input().split()]
#t = [int(x) for x in input().split()]

# 改行区切りの整数の入力
#a = []
#for x in range(n):
#  a.append(int(input()))
#  a.append([int(x) for x in input().split()])
#p = [int(x) for x in input().split()]
#a.sort()
#print(l, file=sys.stderr)

# 文字列の入力
#s = input()

# 出力
#print("{} {}".format(a+b+c, s))
#a.sort()
#print(set(a), file=sys.stderr)
#print(len(set(a)))

#cache = dict()

import re
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
  
def count(c):
  return b // c - (a-1) // c

def doit():
  res = b + 1 - a
  print(res, file=sys.stderr)
  res -= count(c)
  print(res, file=sys.stderr)
  res -= count(d)
  print(res, file=sys.stderr)
  l = lcm(c, d)
  print(l, file=sys.stderr)
  res += count(l)
  print(res, file=sys.stderr)
  return res

#print(doit([0] * 4))
#doit(s)
#print(doit())
try:
  print(doit())
except Exception as e:
  print("e", e, file=sys.stderr)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys;
sys.setrecursionlimit(20000) # 再起呼び出しの最大数をセット

# 整数の入力
#n = int(input())

# スペース区切りの整数の入力
a = [x for x in map(int, input().split())]
#n, y = map(int, input().split())

# 改行区切りの整数の入力
#a = []
#for x in range(n):
#  a.append(int(input()))

# 文字列の入力
#s = input()

# 出力
#print("{} {}".format(a+b+c, s))
#a.sort()
#print(set(a), file=sys.stderr)
#print(len(set(a)))

surfixes = ("dream", "dreamer", "erase", "eraser")

def doit(l):
  #print(s, file=sys.stderr)
  if l == 0:
    return True;
  for x in surfixes:
    if s[:l].endswith(x):
#      return doit(l-len(x))
      if doit(l-len(x)):
        return True
  return False

try:
  if a[0] > 12:
    print("" + [a1])
  elif a[0] > 5:
    print("" + ([a1]/2))
  else
    print("0")
except Exception as e:
  print(e, file=sys.stderr)


Fixed submission:
# -*- coding: utf-8 -*-
import sys;
sys.setrecursionlimit(20000) # 再起呼び出しの最大数をセット

# 整数の入力
#n = int(input())

# スペース区切りの整数の入力
a = [x for x in map(int, input().split())]
#n, y = map(int, input().split())

# 改行区切りの整数の入力
#a = []
#for x in range(n):
#  a.append(int(input()))

# 文字列の入力
#s = input()

# 出力
#print("{} {}".format(a+b+c, s))
#a.sort()
#print(set(a), file=sys.stderr)
print(a, file=sys.stderr)

#surfixes = ("dream", "dreamer", "erase", "eraser")

def doit(l):
  #print(s, file=sys.stderr)
  if l == 0:
    return True;
  for x in surfixes:
    if s[:l].endswith(x):
#      return doit(l-len(x))
      if doit(l-len(x)):
        return True
  return False

try:
  if a[0] > 12:
    print("%d" % a[1])
  elif a[0] > 5:
    print("%d" % (a[1]/2))
  else:
    print("0")
except Exception as e:
  print(e, file=sys.stderr)
Buggy python submission (verdict: Time Limit Exceeded):
#coding utf-8
N=int(input())

roma = [0 for i in range(N)]

for i in range(N):
  tmp=list(input().strip())
  tmp.sort()
  roma[i]=''.join(tmp)

ans=0    
for i in range(N):
  ans +=roma[i+1:].count(roma[i])
    
print(ans)

Fixed submission:
#coding utf-8
N=int(input())

dict={}

ans=0    
for i in range(N):
  tmp = "".join(sorted(input()))
  if tmp not in dict:
    dict[tmp]=0
  else:
    dict[tmp]+=1
    ans+=dict[tmp]
    
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#coding utf-8
N=int(input())

roma = [[0 for i in range(26)] for j in range(N)]

for i in range(N):
  tmp=list(input().strip())
  for j in range(10):
    roma[i][ord(tmp[j])-97] +=1

ans=0    
for i in range(N):
  for j in range(i+1,N):
    if roma[i]==roma[j]:
      ans +=1
    
print(ans)

Fixed submission:
#coding utf-8
N=int(input())

dict={}

ans=0    
for i in range(N):
  tmp = "".join(sorted(input()))
  if tmp not in dict:
    dict[tmp]=0
  else:
    dict[tmp]+=1
    ans+=dict[tmp]
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#coding utf-8
import heapq
N,M=map(int,input().split())
AB= [[int(i) for i in input().split()] for i in range(N)]
work=[]
heapq.heapify(work)
ans=0
for i in range(1,M+1):
  for j in range(N):
    if AB[j][0]==i:
      heapq.heappush(work,-AB[j][1])
  if work:
    tmp=heapq.heappop(work)
    ans-=tmp
  
print(ans)

Fixed submission:
#coding utf-8
import heapq
N,M=map(int,input().split())
AB= [[int(i) for i in input().split()] for i in range(N)]
AB.sort(reverse=True)
work=[]
heapq.heapify(work)
ans=0
for i in range(1,M+1):
  while AB and AB[-1][0] <=i:
      tmp=AB.pop()
      heapq.heappush(work,-tmp[1])
  if work:
    tmp=heapq.heappop(work)
    ans-=tmp
  
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#coding utf-8
S=list(input().strip())
S=[0]+S
mod=10**9+7

dp=[[0 for i in range(13)] for j in range(len(S)+1)]

dp[0][0]=1    
for i in range(len(S)):
  if S[i]=="?":
    for j in range(13):
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]%mod
  else:
    for j in range(13):
      dp[i+1][(j*10+int(S[i]))%13]+=dp[i][j]%mod
    
  
print(dp[-1][5]%mod)  


Fixed submission:
#coding utf-8
S=list(input().strip())
S=[0]+S
l=len(S)
mod=10**9+7

dp=[[0 for i in range(13)] for j in range(l+1)]

dp[0][0]=1    
for i in range(l):
  if S[i]=="?":
    for j in range(13):
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]%mod
  else:
    for j in range(13):
      dp[i+1][(j*10+int(S[i]))%13]+=dp[i][j]%mod

print(dp[-1][5]%mod)
Buggy python submission (verdict: Runtime Error):
#coding utf-8
L,R=map(int,input().split())

tmp=2019//L
ans=0
for i in range(1,tmp+1):
  if i*2019>=L and i*2019<=R:
    print(0)
    break
  if i==tmp:
    print((L%2019*(L+1)%2019)%2019)

Fixed submission:
#coding utf-8
L,R=map(int,input().split())

tmp=99999999999999
if R-L>=2019:
  tmp=0
else:
  for i in range(L%2019,L%2019+R-L):
    for j in range(i+1,L%2019+R-L+1):
      if i==0 or j==0:
        tmp=0
      else:
        if (i*j)%2019<tmp:
          tmp=(i*j)%2019
        
print(tmp)
Buggy python submission (verdict: Runtime Error):
#coding utf-8
N,K=map(int,input().split())
V =list(map(int,input().split())) 

Vl =V
Vr =V[::-1]

dpl=[]
dpr=[]
ansl=[0]
ansr=[0]

for i in range(K):
  if not dpl:
    dpl.append(Vl.pop(0))
  elif min(dpl)<0 and min(dpl)<Vl[i]:
    del dpl[dpl.index(min(dpl))]
  else:
    dpl.append(Vl.pop(0))
  ansl.append(max(sum(dpl),ansl[i]))

for i in range(K):
  if not dpr:
    dpr.append(Vr.pop(0))
  elif min(dpr)<0 and min(dpr)<Vr[i]:
    del dpr[dpr.index(min(dpr))]
  else:
    dpr.append(Vr.pop(0))
  ansr.append(max(sum(dpr),ansr[i]))
    
ans=0    
for i in range(1,K):
  tmp=ansr[i]+ansl[K-i]
  if ans<tmp:
    ans=tmp
  
print(ans)

Fixed submission:
#coding utf-8
N,K=map(int,input().split())
V =list(map(int,input().split())) 

dpl=[]
temp=[]
T =min(N,K)+1
ans=0
for i in range(T):
  for j in range(T-i):
    dpl.clear()
    if i>0:
      dpl.extend(V[0:i])
    if j>0:
      dpl.extend(V[N-j:N])
    dpl.sort()            
    for k in range(K-i-j+1):
      if dpl != [] and k>0:
        if dpl[0]<=0:
          del dpl[0]       
      if ans<sum(dpl):
        ans=sum(dpl)
      if dpl == [] or dpl[0]>0:
        break

print(ans)
Buggy python submission (verdict: Runtime Error):
#coding utf-8
N,M=map(int,input().split())
A=list(map(int,input().split())) 
BC=[[int(i) for i in input().split()] for i in range(M)]
A.sort()
BC.sort(key=lambda x:x[1])
BC.reverse()

k=0
t=0
for i in range(M):
  if t==1 or k==N:
    break
  for j in range(BC[i][0]):
    if BC[i][1]>A[k]:
      A[k]=BC[i][1]
      k+=1
    else:
      t=1
      break
      
      
print(sum(A))    

Fixed submission:
#coding utf-8
N,M=map(int,input().split())
A=list(map(int,input().split())) 
BC=[[int(i) for i in input().split()] for i in range(M)]
A.sort()
BC.sort(key=lambda x:x[1])
BC.reverse()

k=0
t=0
for i in range(M):
  if t==1 or k==N:
    break
  for j in range(BC[i][0]):
    if BC[i][1]>A[k]:
      A[k]=BC[i][1]
      k+=1
      if k==N:
        break
    else:
      t=1
      break
      
      
print(sum(A))

Buggy python submission (verdict: Runtime Error):
#coding utf-8
N,M=map(int,input().split())
A=list(map(int,input().split())) 
BC=[[int(i) for i in input().split()] for i in range(M)]
A.sort()
BC.sort(key=lambda x:x[1])
BC.reverse()

k=0
t=0
for i in range(M):
  if t==1:
    break
  for j in range(BC[i][0]):
    if BC[i][1]>A[k]:
      A[k]=BC[i][1]
      k+=1
    else:
      t=1
      break
      
      
print(sum(A))    

Fixed submission:
#coding utf-8
N,M=map(int,input().split())
A=list(map(int,input().split())) 
BC=[[int(i) for i in input().split()] for i in range(M)]
A.sort()
BC.sort(key=lambda x:x[1])
BC.reverse()

k=0
t=0
for i in range(M):
  if t==1 or k==N:
    break
  for j in range(BC[i][0]):
    if BC[i][1]>A[k]:
      A[k]=BC[i][1]
      k+=1
      if k==N:
        break
    else:
      t=1
      break
      
      
print(sum(A))
Buggy python submission (verdict: Runtime Error):
#conding utf-8
N = int(input())
A = input().split()
ans = 0
t = 0
for i in range(N):
  A[i] = int(A[i])
for i in range(N):
  if A[i] == 0:
    for j in range(N):
      if A[j]<0:
        A[j] = -A[j]
    ans = sum(A)
for j in range(N):
  if A[j]<0:
    t +=1
if t%2 == 0:
  for j in range(N):
    if A[j]<0:
      A[j] = -A[j]
      ans = sum(A)
else:
  for j in range(N):
    if A[j]<0:
      A[j] = -A[j]
  A[A.index(min(A))] = -A[A.index(min(A))]
  ans = sum(A)
      
print(ans)

Fixed submission:
#conding utf-8
ABT =input().split()
a = int(ABT[0])
b = int(ABT[1])
t = int(ABT[2])

x = int(t/a)
print(x*b)
Buggy python submission (verdict: Time Limit Exceeded):
#conding utf-8
x,y,z,k=map(int,input().split())
a=list(map(int,input().split())) 
b=list(map(int,input().split())) 
c=list(map(int,input().split())) 

ab=[]
ans=[]
for i in range(len(a)):
  for j in range(len(b)):
    ab.append(a[i]+b[j])
    
ab.sort()
ab.reverse()
del ab[k:]

for i in range(len(ab)):
  for j in range(len(c)):
    ans.append(ab[i]+c[j])
    
ans.sort()
ans.reverse()

for i in range(k):
  print(ans[i])

Fixed submission:
#conding utf-8
x,y,z,k=map(int,input().split())
a=list(map(int,input().split())) 
b=list(map(int,input().split())) 
c=list(map(int,input().split())) 

ab=[]
ans=[]
for i in range(len(a)):
  for j in range(len(b)):
    ab.append(a[i]+b[j])
    
ab.sort()
ab.reverse()
del ab[k:]

c.sort()
c.reverse()

for i in range(len(ab)):
  for j in range(len(c)):
    ans.append(ab[i]+c[j])
    
ans.sort()
ans.reverse()

for i in range(k):
  print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
#conding utf-8
N,Q=map(int,input().split())
S=input()
lr=[[int(i) for i in input().split()] for i in range(Q)]

AC=[]

for i in range(N-1):
  if S[i:i+2]=="AC":
    AC.append(1)
  else:
    AC.append(0)

for i in range(Q):
  print(sum(AC[lr[i][0]-1:lr[i][1]-1]))

Fixed submission:
#conding utf-8
N,Q=map(int,input().split())
S=input()
lr=[[int(i) for i in input().split()] for i in range(Q)]

AC=[0]
tmp=0
for i in range(N-1):
  if S[i:i+2]=="AC":
    tmp=tmp+1
  AC.append(tmp)

for i in range(Q):
  print(AC[lr[i][1]-1]-AC[lr[i][0]-1])

Buggy python submission (verdict: Time Limit Exceeded):
#conding utf-8
N,Q=map(int,input().split())
S=input()
lr=[[int(i) for i in input().split()] for i in range(Q)]

AC=[0 for i in range(N)]

for i in range(N-1):
  if S[i:i+2]=="AC":
    AC[i]=1
    i=i+1

for i in range(Q):
  print(sum(AC[lr[i][0]-1:lr[i][1]-1]))


Fixed submission:
#conding utf-8
N,Q=map(int,input().split())
S=input()
lr=[[int(i) for i in input().split()] for i in range(Q)]

AC=[0]
tmp=0
for i in range(N-1):
  if S[i:i+2]=="AC":
    tmp=tmp+1
  AC.append(tmp)

for i in range(Q):
  print(AC[lr[i][1]-1]-AC[lr[i][0]-1])

Buggy python submission (verdict: Time Limit Exceeded):
#conding utf-8
N,Q=map(int,input().split())
S=input()
lr=[[int(i) for i in input().split()] for i in range(Q)]

AC=[0 for i in range(N)]

for i in range(N-1):
  if S[i:i+2]=="AC":
    AC[i]=1

for i in range(Q):
  print(sum(AC[lr[i][0]-1:lr[i][1]-1]))

Fixed submission:
#conding utf-8
N,Q=map(int,input().split())
S=input()
lr=[[int(i) for i in input().split()] for i in range(Q)]

AC=[0]
tmp=0
for i in range(N-1):
  if S[i:i+2]=="AC":
    tmp=tmp+1
  AC.append(tmp)

for i in range(Q):
  print(AC[lr[i][1]-1]-AC[lr[i][0]-1])