Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N = int(input())
H = list(map(int, input().split()))
for i in range(N-1):
  if H[i] > H[i+1] + 1:
    print("No")
    exit()
  elif H[i] <= H[i+1]:
    if i > 0:
      if H[i-1] <= H[i]-1:
        H[i] -= 1        
  elif H[i] == H[i+1] + 1:
    H[i] -= 1
    if i > 0:
      if H[i-1] > H[i]:
        print("No")
        exit()
print("Yes")

Fixed submission:
s = input()
# RR...RL...LLとなる文字列ssに分割して考える
import math
# len(ss) % 2 == 0 の場合は、境界にlen(ss)/2ずつ
# 奇数の場合は、ss[0]大、ss[1]小、→ss[偶数]大、ss[奇数]小
ans = [0] * len(s)
ss = []
start = 0
for i in range(len(s) - 1):
  if (s[i]=="L" and s[i+1]=="R"):
    ss.append(s[start:i+1])
    start = i+1
  elif i == len(s) - 2:
    ss.append(s[start:i+2])  
#print(ss)
# rlposはr,lの位置
sumlenj = 0
for j in ss: 
  rlpos = j.find("RL")
  if len(j) % 2 == 0:
    ans[sumlenj+rlpos] = int(len(j)/2)
    ans[sumlenj+rlpos+1] = int(len(j)/2)
  else:
    if rlpos % 2 == 0:
      ans[sumlenj+rlpos] = int(math.ceil(len(j)/2))
      ans[sumlenj+rlpos+1] = int(math.floor(len(j)/2))
    else:
      ans[sumlenj+rlpos] = int(math.floor(len(j)/2))
      ans[sumlenj+rlpos+1] = int(math.ceil(len(j)/2))
  sumlenj += len(j)
print(*ans)
Buggy python submission (verdict: Runtime Error):
MOD = 10 ** 9 + 7

S = input()
N = len(S)

dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1

mul = 1

for i, x in enumerate(S[::-1]):
  if x == "?":
    for k in range(10):
      for j in range(13):
        dp[i + 1][(mul * k + j) % 13] += dp[i][j]
        dp[i + 1][(mul * k + j) % 13] %= MOD
  else:
    k = int(x)
    for j in range(13):
      dp[i + 1][(mul * k + j) % 13] += dp[i][j]
      dp[i + 1][(mul * k + j) % 13] %= MOD

  mul = mul * 10

print(dp[N][5])

Fixed submission:
A, B = map(int,input().split())
if (A + B) % 2 == 0: 
  print(int((A+B)/2))
else:
  print("IMPOSSIBLE")
Buggy python submission (verdict: Time Limit Exceeded):
# D - Digits Parade
# https://atcoder.jp/contests/abc135/tasks/abc135_d

S = input()
n = len(S)

MOD = 10 ** 9 + 7

# dp[i][j] i桁目まででj余る数
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1

for i, s in enumerate(S):
  for j in range(10):
    if s == "?" or int(s) == j:
      for k in range(13):
        dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
  for k in range(13):
    dp[i + 1][k] %= MOD

print(dp[n][5])


Fixed submission:
MOD = 10 ** 9 + 7

S = input()
N = len(S)

dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1

mul = 1

for i, x in enumerate(S[::-1]):
  if x == "?":
    for k in range(10):
      for j in range(13):
        jj = (mul * k + j) % 13
        dp[i + 1][jj] += dp[i][j]
        dp[i + 1][jj] %= MOD
  else:
    k = int(x)
    for j in range(13):
      jj = (mul * k + j) % 13
      dp[i + 1][jj] += dp[i][j]
      dp[i + 1][jj] %= MOD

  mul = (mul * 10) % 13

print(dp[N][5])

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7

S = input()
N = len(S)

dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1

mul = 1

for i, x in enumerate(S[::-1]):
  if x == "?":
    for k in range(10):
      for j in range(13):
        dp[i + 1][(mul * k + j) % 13] += dp[i][j]
        dp[i + 1][(mul * k + j) % 13] %= MOD
  else:
    k = int(x)
    for j in range(13):
      dp[i + 1][(mul * k + j) % 13] += dp[i][j]
      dp[i + 1][(mul * k + j) % 13] %= MOD

  mul = mul * 10

print(dp[N][5])

Fixed submission:
MOD = 10 ** 9 + 7

S = input()
N = len(S)

dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1

mul = 1

for i, x in enumerate(S[::-1]):
  if x == "?":
    for k in range(10):
      for j in range(13):
        jj = (mul * k + j) % 13
        dp[i + 1][jj] += dp[i][j]
        dp[i + 1][jj] %= MOD
  else:
    k = int(x)
    for j in range(13):
      jj = (mul * k + j) % 13
      dp[i + 1][jj] += dp[i][j]
      dp[i + 1][jj] %= MOD

  mul = (mul * 10) % 13

print(dp[N][5])

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7

S = input()
N = len(S)

dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1

mul = 1

for i, x in enumerate(S[::-1]):
  if x == "?":
    for k in range(10):
      for j in range(13):
        dp[i + 1][(mul * k + j) % 13] += dp[i][j]
        dp[i + 1][(mul * k + j) % 13] %= MOD
  else:
    k = int(x)
    for j in range(13):
      dp[i + 1][(mul * k + j) % 13] += dp[i][j]
      dp[i + 1][(mul * k + j) % 13] %= MOD

  mul = mul * 10

print(dp[N][5])

Fixed submission:
MOD = 10 ** 9 + 7

S = input()
N = len(S)

dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1

mul = 1

for i, x in enumerate(S[::-1]):
  if x == "?":
    for k in range(10):
      for j in range(13):
        jj = (mul * k + j) % 13
        dp[i + 1][jj] += dp[i][j]
        dp[i + 1][jj] %= MOD
  else:
    k = int(x)
    for j in range(13):
      jj = (mul * k + j) % 13
      dp[i + 1][jj] += dp[i][j]
      dp[i + 1][jj] %= MOD

  mul = (mul * 10) % 13

print(dp[N][5])
Buggy python submission (verdict: Runtime Error):
inf = 10**9
 
S = int(input())
 
if S == 10 ** 18:
    print(0, 0, inf, 0, M, inf)
else:
    S1 = S // inf + 1
    S2 = inf - (S % inf)
 
    print(0, 0, S1, 1, S2, inf)

Fixed submission:
inf = 10**9
 
S = int(input())
 
if S == 10 ** 18:
    print(0, 0, inf, 0, inf, inf)
else:
    S1 = S // inf + 1
    S2 = inf - (S % inf)
 
    print(0, 0, S1, 1, S2, inf)

Buggy python submission (verdict: Time Limit Exceeded):
import math
S = int(input())
a = math.ceil(S ** (1/2))
for i in range(1, a + 1):
  b = S / i
#  print(b)
  if b % 1 == 0 and b <= 10**9:
    print(0,0,0,i,int(b),0)
    exit()

Fixed submission:
inf = 10**9
 
S = int(input())
 
if S == 10 ** 18:
    print(0, 0, inf, 0, inf, inf)
else:
    S1 = S // inf + 1
    S2 = inf - (S % inf)
 
    print(0, 0, S1, 1, S2, inf)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import numpy as np
N = int(input())
A = [int(input()) for _ in range(N)]

# d = deque()
R = deque(A)
R.append(0)
L = deque([0])

maxA = np.max(R)
for i in A:
  R.popleft()
  if i >= maxA: 
    maxA = max(np.max(L), np.max(R))
  print(maxA)
  L.append(i)
  

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]
B = A[:]
B.sort(reverse=True)
# print(A)
fmax = B[0]
smax = B[1]
for i in A:
  if i == fmax:
    print(smax)
  else:
    print(fmax)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import numpy as np
N = int(input())
A = [int(input()) for _ in range(N)]

# d = deque()
R = deque(A)
R.append(0)
L = deque([0])

for i in A:
  R.popleft()
  print(max(np.max(L), np.max(R)))
  L.append(i)
  

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]
B = A[:]
B.sort(reverse=True)
# print(A)
fmax = B[0]
smax = B[1]
for i in A:
  if i == fmax:
    print(smax)
  else:
    print(fmax)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]

# d = deque()
R = deque(A)
R.append(0)
L = deque([0])

for i in A:
  R.popleft()
  print(max(max(L), max(R)))
  L.append(i)
  

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]
B = A[:]
B.sort(reverse=True)
# print(A)
fmax = B[0]
smax = B[1]
for i in A:
  if i == fmax:
    print(smax)
  else:
    print(fmax)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]

# d = deque()
R = deque(A)
R.append(0)
L = deque([0])

for i in A:
  R.popleft()
  print(max(max(L), max(R)))
  L.append(i)
  

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]
B = A[:]
B.sort(reverse=True)
# print(A)
fmax = B[0]
smax = B[1]
for i in A:
  if i == fmax:
    print(smax)
  else:
    print(fmax)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]
# print(A)
for i, v in enumerate(A):
  mylist = A[:]
  mylist[i:i+1] = []
  # print(mylist)
  print(max(mylist))

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]
B = A[:]
B.sort(reverse=True)
# print(A)
fmax = B[0]
smax = B[1]
for i in A:
  if i == fmax:
    print(smax)
  else:
    print(fmax)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
aset = set(a)

if len(aset) == 1:
  if all(i == 0 for i in a):
    print("Yes")
  else:
    print("No")
elif len(aset) == 2:
  a1, a2 = sorted(aset)
  if a1 == 0:
    if a.count(a1) * 3 == N:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
elif len(aset) == 3:
  a1, a2, a3 = aset
  if a.count(a1) == a.count(a2) == a.count(a3):
    if a1 ^ a2 == a3:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  print("No")


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
aset = set(a)

if len(aset) == 1:
  if all(i == 0 for i in a):
    print("Yes")
  else:
    print("No")
elif len(aset) == 2:
  a1, a2 = sorted(aset)
  if a1 == 0:
    if a.count(a1) * 3 == n:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
elif len(aset) == 3:
  a1, a2, a3 = aset
  if a.count(a1) == a.count(a2) == a.count(a3):
    if a1 ^ a2 == a3:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
aset = set(a)

if len(aset) == 1:
  if all(i == 0 for i in a):
    print("Yes")
  else:
    print("No")
elif len(aset) == 2:
  a1, a2 = sorted(aset):
  if a1 == 0:
    if a.count(a1) * 3 == N:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
elif len(aset) == 3:
  a1, a2, a3 = aset
  if a.count(a1) == a.count(a2) == a.count(a3):
    if a1 ^ a2 = a3:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  print("No")

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
aset = set(a)

if len(aset) == 1:
  if all(i == 0 for i in a):
    print("Yes")
  else:
    print("No")
elif len(aset) == 2:
  a1, a2 = sorted(aset)
  if a1 == 0:
    if a.count(a1) * 3 == n:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
elif len(aset) == 3:
  a1, a2, a3 = aset
  if a.count(a1) == a.count(a2) == a.count(a3):
    if a1 ^ a2 == a3:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  print("No")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

from collections import deque
dA = deque(A)
ans=[]
for i in range(N):
  Nans = 0
  for itr, val in enumerate(dA):
    if itr % 2 == 0:
      Nans += val
    else:
      Nans -= val
  ans.append(Nans)
  aa = dA.popleft()
  dA.append(aa)
print(' '.join(map(str, ans)))

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

from collections import deque
dA = deque(A)
ans= deque([])
Nans = 0
for itr, val in enumerate(dA):
  if itr % 2 == 0:
    Nans += val
  else:
    Nans -= val
ans.append(Nans)

for i in A:
  Nans = 2*i - Nans
  ans.append(Nans)
ans.pop()
print(' '.join(map(str, ans)))
Buggy python submission (verdict: Runtime Error):
c = 10**9+7

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

def combinations_count_mod(n, r, c):
  r = min(n-r,r)
  if r == 0: return 1
  ret = 1
  for j in range(r):
    ret *= (n-j)/(r-j) % c
  return ret

for i in range(1, k+1):
  a = combinations_count_mod(k-1, i-1, c) 
  if n-k >= i-1:
    b = (combinations_count_mod(n-k+1, i, c))
  else:
    b = 0
  print(int((a*b) % c))


Fixed submission:
import math
c = 10**9+7

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

def combinations_count(n, r):
  if n <= r:
    return 1
  else:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1, k+1):
  a = combinations_count(k-1, i-1) 
  if n-k >= i-1:
    b = combinations_count(n-k+1, i)
  else:
    b = 0
  print(int((a*b) % c))

Buggy python submission (verdict: Runtime Error):
c = 10**9+7

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

def combinations_count_mod(n, r, c):
  ret = 1
  for j in range(r):
    ret *= (n-j)/(r-j) % c
  return ret

for i in range(1, k+1):
  a = combinations_count_mod(k-1, i-1, c) 
  if n-k >= i-1:
    b = (combinations_count_mod(n-k+1, i, c))
  else:
    b = 0
  print(int((a*b) % c))

Fixed submission:
import math
c = 10**9+7

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

def combinations_count(n, r):
  if n <= r:
    return 1
  else:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1, k+1):
  a = combinations_count(k-1, i-1) 
  if n-k >= i-1:
    b = combinations_count(n-k+1, i)
  else:
    b = 0
  print(int((a*b) % c))

Buggy python submission (verdict: Runtime Error):
c = 10**9+7

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

def combinations_count_mod(n, r):
  ret = 1
  for i in range(r):
    ret *= (n-i)/(r-i) % c
  return ret

for i in range(1, k+1):
  a = combinations_count_mod(k-1, i-1) 
  if n-k > i-1:
#    if n-k-i >= 1:
    b = (combinations_count_mod(n-k-1, i-1) * ((n-k-1-(i-1))/i + 2)) 
#    else:
#      b = (n-k-1) * 3
  elif n-k == i-1:
    b = 1
  else:
    b = 0
  print(int((a*b) % c))

Fixed submission:
import math
c = 10**9+7

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

def combinations_count(n, r):
  if n <= r:
    return 1
  else:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1, k+1):
  a = combinations_count(k-1, i-1) 
  if n-k >= i-1:
    b = combinations_count(n-k+1, i)
  else:
    b = 0
  print(int((a*b) % c))
Buggy python submission (verdict: Runtime Error):
c = 10**9+7

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

def combinations_count_mod(n, r):
  ret = 1
  for i in range(r):
    ret *= (n-i)/(r-i) % c
  return ret

for i in range(1, k+1):
  a = combinations_count_mod(k-1, i-1) 
  if n-k > i-1:
#    if n-k-i >= 1:
    b = (combinations_count_mod(n-k-1, i-1) * ((n-k-1-(i-1))/i + 2)) 
#    else:
#      b = (n-k-1) * 3
  elif n-k == i-1:
    b = 1
  else:
    b = 0
  print(int((a*b) % c))

Fixed submission:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1])
timeSum = 0
for i in AB:
  timeSum += i[0]
  if timeSum > i[1]:
    print("No")
    exit()
print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [[0] * (m + 1) for _ in range(n + 1)]
sum = [[0] * (m + 1) for _ in range(n + 1)]
MOD = 10 ** 9 + 7

ans = 0
for i in range(n):
  for j in range(m):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = (sum[i][j] + 1) % MOD
    else:
      dp[i + 1][j + 1] = 0
    sum[i + 1][j + 1] = (sum[i][j + 1] + sum[i + 1][j] 
                       - sum[i][j] + dp[i + 1][j + 1]) % MOD
    ans += dp[i + 1][j + 1]
    ans %= MOD
print((ans + 1) % MOD)


Fixed submission:
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [[0] * (m + 1) for _ in range(n + 1)]
sum = [[0] * (m + 1) for _ in range(n + 1)]
MOD = 10 ** 9 + 7

ans = 0
for i in range(n):
  for j in range(m):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = (sum[i][j] + 1) % MOD
    else:
      dp[i + 1][j + 1] = 0
    sum[i + 1][j + 1] = (sum[i][j + 1] + sum[i + 1][j] 
                       - sum[i][j] + dp[i + 1][j + 1]) % MOD
    ans += dp[i + 1][j + 1]
    ans %= MOD
print((ans + 1) % MOD)
Buggy python submission (verdict: Runtime Error):
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
 
import itertools
hoges = {}
for i in itertools.combinations(xy, 2):
    if i[0][0] - i[1][0] >= 0:
        hoge = (i[0][0] - i[1][0], i[0][1] - i[1][1])
    else:
        hoge = (i[1][0] - i[0][0], i[1][1] - i[0][1])
    hoges.setdefault(hoge, 0)
    hoges[hoge] += 1
# print(hoges)
max_v = max(hoges.values())
print(N - max_v)

Fixed submission:
from itertools import combinations
from collections import Counter

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

cXY = combinations(XY, 2)

edge = []
for a, b in cXY:
  edge.append((a[0]-b[0], a[1]-b[1]))
  edge.append((-a[0]+b[0], -a[1]+b[1]))

ce = Counter(edge)

if N == 1:
  ans = 1
else:
  dup = max(ce.values())
  ans = N - dup
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

#print(N, Q)
#print(STX)
#print(D)

for d in D:
  mindist = 10 ** 9
  for x in STX:
    if x[0] < x[2] + d + 0.5 < x[1]:
      if x[2] < mindist:
        mindist = x[2]
  if mindist == 10 ** 9:
    print(-1)
  else:
    print(mindist)

Fixed submission:
# E - Roadwork
# https://atcoder.jp/contests/abc128/tasks/abc128_e

from heapq import heappop, heappush
from collections import defaultdict

n, q = map(int,input().split())
task = []
for _ in range(n): 
  s, t, x = map(int, input().split())
  task.append((t - x, 0, x)) 
  task.append((s - x, 1, x)) 

for i in range(q):
  d = int(input())
  task.append((d, 2, i)) 

answer = [-1] * q

task.sort()

se = set()
se_hp = []

for a, b, c in task:
  if b == 0:
    se.remove(c)
  elif b == 1:
    se.add(c)
    heappush(se_hp, c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str, answer)))
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(m)]
ans = set(range(1, n + 1))

for l, r in LR:
  ans &= set(range(l, r + 1))
  
print(len(ans))

Fixed submission:
N, M = map(int, input().split())
minNum = 1
maxNum = N
for lr in range(M):
  l, r = map(int, input().split())
  if minNum <= l and r <= maxNum:
    minNum = l
    maxNum = r
  elif minNum <= l <= maxNum and maxNum <= r:
    minNum = l
  elif l <= minNum and minNum <= r <= maxNum:
    maxNum = r
  elif r < minNum or maxNum < l:
    print("0")
    exit()
#  print(l,r,minNum,maxNum)
print(maxNum - minNum +1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
li = [i for i in range(1, N+1)]
ans = li
for lr in range(M):
  l, r = map(int, input().split())
  ans = [i for i in ans if l <= i <= r]
print(len(ans))

Fixed submission:
N, M = map(int, input().split())
minNum = 1
maxNum = N
for lr in range(M):
  l, r = map(int, input().split())
  if minNum <= l and r <= maxNum:
    minNum = l
    maxNum = r
  elif minNum <= l <= maxNum and maxNum <= r:
    minNum = l
  elif l <= minNum and minNum <= r <= maxNum:
    maxNum = r
  elif r < minNum or maxNum < l:
    print("0")
    exit()
#  print(l,r,minNum,maxNum)
print(maxNum - minNum +1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
li = [i for i in range(1, N+1)]
ans = li
for lr in LR:
  ans = [i for i in ans if lr[0] <= i <= lr[1]]
print(len(ans))

Fixed submission:
N, M = map(int, input().split())
minNum = 1
maxNum = N
for lr in range(M):
  l, r = map(int, input().split())
  if minNum <= l and r <= maxNum:
    minNum = l
    maxNum = r
  elif minNum <= l <= maxNum and maxNum <= r:
    minNum = l
  elif l <= minNum and minNum <= r <= maxNum:
    maxNum = r
  elif r < minNum or maxNum < l:
    print("0")
    exit()
#  print(l,r,minNum,maxNum)
print(maxNum - minNum +1)
Buggy python submission (verdict: Runtime Error):
import heapq
n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

tank = []

idx = 0
while (len(tank) < n + 1) and (idx < m):
  for _ in range(BC[idx][0]): 
    heapq.heappush(tank, -BC[idx][1])
  idx +=  1

# print(A)
# print(BC)
# print(tank)

ans = 0
p = -heapq.heappop(tank)
for a in A:
  if p > a:
    ans += p
    p = -heapq.heappop(tank)
  else:
    ans += a

print(ans)
    
    

Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

A.sort()
BC.sort(key=lambda x: x[1],reverse=True)

ans = 0
cnt = 0
for i in BC:
  for _ in range(i[0]):
#    print(len(A), cnt)
    if A[cnt] < i[1]:
      ans += i[1]
    else:
      ans += A[cnt]
    cnt += 1
    if len(A) < cnt+1:
      print(ans)
      exit()
#    print(i, _, ans, cnt)
if cnt  < len(A):
  ans += sum(A[cnt - len(A):])

#print(A)
#print(BC)
print(ans)
Buggy python submission (verdict: Runtime Error):
def dfs(i):
    if all([v != -1 for v in visited]):
        return
    color = visited[i]
    for nextIdx, wgt in graph[i]:
        if visited[nextIdx] == -1:
            if wgt % 2 == 0:
                visited[nextIdx] = color
            else:
                visited[nextIdx] = int(not color)
            dfs(nextIdx)

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

visited = [-1] * n
visited[0] = 0
dfs(0)
for v in visited:
    print(v)


Fixed submission:
import sys
sys.setrecursionlimit(20000000)

def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance + edge_size) % 2)
            dfs(next_node, distance + edge_size)

N = int(input())

G = [[] for i in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    G[u - 1].append([v - 1, w])
    G[v - 1].append([u - 1, w])

ans = [-1] * N
dfs(0, 0)
print(*ans, sep='\n')

Buggy python submission (verdict: Runtime Error):
def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance + edge_size) % 2)
            dfs(next_node, distance + edge_size)

N = int(input())

G = [[] for i in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    G[u - 1].append([v - 1, w])
    G[v - 1].append([u - 1, w])

ans = [-1] * N
dfs(0, 0)
print(*ans, sep='\n')

Fixed submission:
import sys
sys.setrecursionlimit(20000000)

def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance + edge_size) % 2)
            dfs(next_node, distance + edge_size)

N = int(input())

G = [[] for i in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    G[u - 1].append([v - 1, w])
    G[v - 1].append([u - 1, w])

ans = [-1] * N
dfs(0, 0)
print(*ans, sep='\n')
Buggy python submission (verdict: Runtime Error):
R, G, B ,N = map(int, input().split())

cnt = 0
for r in range(N//R + 1):
  for g in range((N-r*R)//G + 1):
    val = N - (r*R + g*G)
    if val % B == 0 and  val >= 0:
      cnt += 1
print(cnt)


Fixed submission:
N, K = map(int, input().split())
print(N-K+1)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
from functools import reduce

n = int(input()) 
alist = list(map(int, input().split()))
 
def gcd2(a,b):
  while b!=0:
    a,b=b,a%b
  return a

def gcd(*numbers):
    return reduce(gcd2, numbers)

if len(alist) == 2:
  ans = max(alist)
else:
  ansList = []
  for i in range(len(alist)):
    srList = alist[:]
    del srList[i]
    gcdval = gcd(*srList)
    ansList.append(gcdval)
  ans = max(ansList)
print("{}".format(ans))

Fixed submission:
from fractions import gcd
N = int(input())
a = list(map(int, input().split()))
l = [0] * N
r = [0] * N
m = [0] * N

for i in range(N):
  if i == 0:
    l[i] = 0
  else:
    l[i] = gcd(l[i-1], a[i-1])

for j in reversed(range(N)):
  if j == N - 1:
    r[j] = 0
  else:
    r[j] = gcd(r[j+1], a[j+1])
    
for k in range(N):
#  print(r[k], l[k])
  m[k] = gcd(r[k], l[k])
  
print(max(m))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

def countHand(st, pos):
  left_b = st[:pos].count('#')
  right_w = st[pos:].count('.')
  count = left_b + right_w
  return count
  
minHand = 2 * 10 **5
for i in range(len(S)+1):
  ret = countHand(S, i) 
  if ret <= minHand:
    minHand = ret

ans = minHand
print("{}".format(ans))

Fixed submission:
N = int(input())
S = input()

# at position 0
l_b = 0
r_w = S.count('.')

needHand = l_b + r_w
for i in S:
  if i == '#': #black
    l_b += 1
  else:
    r_w -= 1  
  needHand = min(needHand, l_b + r_w)

ans = needHand
print("{}".format(ans))