Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, A, B = map(int, input().split())
p = N//(A + B) + 1

balls = ("b"*A + "r"*B)*p

if "r" in balls:
  print(len(balls[0:N].replace("r","")))
else:
  print(len(balls[0:N]))


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

a = N//(A + B)
b = N%(A + B)

if A <= b:
  print(a*A + A)
else:
  print(a*A + b)

Buggy python submission (verdict: Runtime Error):
N, A, B = map(int, input().split())
p = N//(A + B) + 1

balls = ("b"*A + "r"*B)*p
print(len(balls[0:N].replace("r","")))


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

a = N//(A + B)
b = N%(A + B)

if A <= b:
  print(a*A + A)
else:
  print(a*A + b)

Buggy python submission (verdict: Runtime Error):
N, A, B = map(int, input().split())
p = N//(A + B) + 1

balls = ("b"*A + "r"*B)*p

print(len(balls[0:N].replace("r","")))


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

a = N//(A + B)
b = N%(A + B)

if A <= b:
  print(a*A + A)
else:
  print(a*A + b)

Buggy python submission (verdict: Runtime Error):
N, A, B = map(int, input().split())

balls = ""

while len(balls) < N:
  balls += "b"*A + "r"*B

print(len(balls[0:N].replace("r","")))

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

a = N//(A + B)
b = N%(A + B)

if A <= b:
  print(a*A + A)
else:
  print(a*A + b)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
sc = [list(map(int, input().split())) for i in range(M)]
cnt = 0
ans = []
if N == 1:
  for i in range(10):
    i = str(i)
    for j in range(M):
      if i[sc[j][0] - 1] == str(c = sc[j][1]):
        cnt += 1
    if cnt == M:
      ans.append(int(i))
    cnt = 0
else:
  for i in range(10**(N-1), 10**N):
    i = str(i)
    for j in range(M):
      if i[sc[j][0] - 1] == str(sc[j][1]):
        cnt += 1
    if cnt == M:
      ans.append(int(i))
    cnt = 0

#print(ans)
print(min(ans) if ans else -1)

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

keta = [0,0,0]
DP = [0,0,0]

for i in sc:
  s = i[0]
  c = i[1]
  if DP[-1*N+s-1] == 0 or (DP[-1*N+s-1] == 1 and keta[-1*N+s-1] == c):
    keta[-1*N+s-1] = c
    DP[-1*N+s-1] = 1
  else:
    DP[-1*N+s-1] = -1
    
if keta[-1*N] == 0:
  if DP[-1*N] == 1 and N != 1:
    DP[-1*N] = -1
  elif N != 1:
    keta[-1*N] = 1
    DP[-1*N] = 1
  else:
    DP[-1*N] = 1
  
if -1 in DP:
  print(-1)
else:
  ans = ''
  for i in keta:
    ans += str(i)
  print(int(ans[3-N:]))
#print(DP)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = [input() for i in range(N)]
S.sort()

dic = {}
for i in S:
  dic[i] = 0
for i in S:
  dic[i] += 1
for i in dic:
  if dic[i] == max(dic.values()):
    print(i)

Fixed submission:
N = int(input())
S = [input() for i in range(N)]
S.sort()

dic = {}
for i in S:
  dic[i] = 0
for i in S:
  dic[i] += 1
M = max(dic.values())
for i in dic:
  if dic[i] == M:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = [input() for i in range(N)]

dic = {i:0 for i in S}
  
for i in S:
  dic[i] += 1
  
ans = [] 
for i in dic:
  if dic[i] == max(dic.values()):
    ans.append(i)
ans.sort()
for i in ans:
  print(i)

Fixed submission:
N = int(input())
S = [input() for i in range(N)]
S.sort()

dic = {}
for i in S:
  dic[i] = 0
for i in S:
  dic[i] += 1
M = max(dic.values())
for i in dic:
  if dic[i] == M:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
import math

N, K = map(int, input().split())
h = [0] + list(map(int, input().split()))

DP = [math.inf] * (N+1)

for i in range(1, N+1):
    if i == 1:
        DP[i] = 0
        continue
    if i == 2:
        DP[i] = abs(h[1] - h[2])
        continue
    for j in range(1, min(i, K) + 1):
        DP[i] = min(DP[i], DP[i-j] + abs(h[i-j] - h[i]))


print(DP[N])



Fixed submission:
import math

N, K = map(int, input().split())
h = [0] + list(map(int, input().split()))

DP = [math.inf] * (N+1)

for i in range(1, N+1):
    if i == 1:
        DP[i] = 0
        continue
    if i == 2:
        DP[i] = abs(h[1] - h[2])
        continue
    for j in range(1, min(i, K) + 1):
        DP[i] = min(DP[i], DP[i-j] + abs(h[i-j] - h[i]))


print(DP[N])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())

DP = [[0] * (W + 1) for _ in range(N+1)]

for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(1, W+1):
        DP[i][j] = max(DP[i][j-1], DP[i-1][j])
        if j - w >= 0:
            DP[i][j] = max(DP[i][j], DP[i-1][j-w] + v)

print(DP[N][W])


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

DP = [[0] * (W + 1) for _ in range(N+1)]

for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(1, W+1):
        DP[i][j] = max(DP[i][j-1], DP[i-1][j])
        if j - w >= 0:
            DP[i][j] = max(DP[i][j], DP[i-1][j-w] + v)

print(DP[N][W])
Buggy python submission (verdict: Time Limit Exceeded):
import math

N, W = map(int, input().split())

DP = [[math.inf] * 100001 for _ in range(N+1)]
DP[0][0] = 0
for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(100001):
        if j >= v:
            DP[i][j] = min(DP[i-1][j], DP[i-1][j-v]+w)
        else:
            DP[i][j] = DP[i-1][j]

ans = 100000
while DP[N][ans] > W:
    ans -= 1
print(ans)


Fixed submission:
import math

N, W = map(int, input().split())

DP = [[math.inf] * 100001 for _ in range(N+1)]
DP[0][0] = 0
for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(100001):
        if j >= v:
            DP[i][j] = min(DP[i-1][j], DP[i-1][j-v]+w)
        else:
            DP[i][j] = DP[i-1][j]

ans = 100000
while DP[N][ans] > W:
    ans -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input().strip())
ans = int(1)
a = map(int, input().strip().split());
for i in a:
	ans *= i
if ans > int(1e18):
	print(-1)
else:
	print(ans)

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

	if 0 in A:
		print(0)
		return

	prod = 1
	for a in A:
		prod *= a
		if prod > int(1e18):
			print(-1)
			return

	print(prod)

main()

Buggy python submission (verdict: Runtime Error):
n = int(input())
ans = 1
for i in range(0, n):
	t = int(input())
	ans *= t
if ans > int(1e18):
	print(-1)
else:
	print(ans)

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

	if 0 in A:
		print(0)
		return

	prod = 1
	for a in A:
		prod *= a
		if prod > int(1e18):
			print(-1)
			return

	print(prod)

main()
Buggy python submission (verdict: Runtime Error):
def main():
    X, K, D = list(map(int, input().split()))
    right = X % D
    left = right - D
    if X in [left, right]:
        if K % 2 == 0:
            print(abs(X))
        else:
            if X == left:
                print(right)
            else:
                print(abs(left))
        return
    if X > right:
        to_right = (X - right) // D
        if to_right >= K:
            print(X - K * D)
        else: # to_right < K
            if (K - to_right) % 2 == 0:
                print(right)
            else:
                print(abs(left))
    else:  # X < left
        to_left = (left - X) // D
        if to_left >= K:
            print(abs(X + K * D))
        else: # to_left < K
            if (K - to_right) % 2 == 0:
                print(abs(left))
            else:
                print(right)


if __name__ == '__main__':
    main()

Fixed submission:

def main():
    X, K, D = list(map(int, input().split()))
    right = X % D
    left = right - D
    if X in [left, right]:
        if K % 2 == 0:
            print(abs(X))
        else:
            if X == left:
                print(right)
            else:
                print(abs(left))
        return
    if X > right:
        to_right = (X - right) // D
        if to_right >= K:
            print(X - K * D)
        else: # to_right < K
            if (K - to_right) % 2 == 0:
                print(right)
            else:
                print(abs(left))
    else:  # X < left
        to_left = (left - X) // D
        if to_left >= K:
            print(abs(X + K * D))
        else: # to_left < K
            if (K - to_left) % 2 == 0:
                print(abs(left))
            else:
                print(right)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    R, C, K = list(map(int, input().split()))
    # dp[r][c][n]: r行目でn個のアイテムを拾う場合の(r, c)でのアイテムの価値の合計の最大
    dp = [[[0 for _ in range(4)] for _ in range(C)] for _ in range(R)]
    V = [[0 for _ in range(C)] for _ in range(R)]
    for _ in range(K):
        r, c, v = list(map(int, input().split()))
        V[r - 1][c - 1] = v
    dp[0][0][1] = V[0][0]
    for r in range(R):
        for c in range(C):
            if r == c == 0:
                continue
            v_rc = V[r][c]
            max_dp_before_row = 0 if r == 0 else max(dp[r - 1][c])
            # dp[r][c][0]
            v1 = 0 if c == 0 else dp[r][c - 1][0]
            dp[r][c][0] = max(v1, max_dp_before_row)
            # dp[r][c][1]
            v1 = 0 if c == 0 else max(dp[r][c - 1][1], dp[r][c - 1][0] + v_rc)
            v2 = 0 if r == 0 else (max_dp_before_row + v_rc)
            dp[r][c][1] = max(v1, v2)
            # dp[r][c][2], dp[r][c][3]
            for n in range(2, 4):
                dp[r][c][n] = 0 if c == 0 else max(dp[r][c - 1][n], dp[r][c - 1][n - 1] + v_rc)
    print(max(dp[R-1][C-1]))


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    R, C, K = list(map(int, input().split()))
    # dp[r][c][n]: r行目でn個のアイテムを拾う場合の(r, c)でのアイテムの価値の合計の最大
    dp_0 = [[0 for _ in range(C)] for _ in range(R)]
    dp_1 = [[0 for _ in range(C)] for _ in range(R)]
    dp_2 = [[0 for _ in range(C)] for _ in range(R)]
    dp_3 = [[0 for _ in range(C)] for _ in range(R)]
    V = [[0 for _ in range(C)] for _ in range(R)]
    for _ in range(K):
        r, c, v = list(map(int, input().split()))
        V[r - 1][c - 1] = v
    dp_1[0][0] = V[0][0]
    for r in range(R):
        for c in range(C):
            if r == c == 0:
                continue
            v_rc = V[r][c]
            max_dp_before_row = 0 if r == 0 else max(dp_0[r - 1][c], dp_1[r - 1][c], dp_2[r - 1][c], dp_3[r - 1][c])
            # dp[r][c][0]
            v1 = 0 if c == 0 else dp_0[r][c - 1]
            dp_0[r][c] = max(v1, max_dp_before_row)
            # dp[r][c][1]
            v1 = 0 if c == 0 else max(dp_1[r][c - 1], dp_0[r][c - 1] + v_rc)
            v2 = 0 if r == 0 else (max_dp_before_row + v_rc)
            dp_1[r][c] = max(v1, v2)
            # dp[r][c][2], dp[r][c][3]
            dp_2[r][c] = 0 if c == 0 else max(dp_2[r][c - 1], dp_1[r][c - 1] + v_rc)
            dp_3[r][c] = 0 if c == 0 else max(dp_3[r][c - 1], dp_2[r][c - 1] + v_rc)
    print(max(dp_0[R-1][C-1], dp_1[R-1][C-1], dp_2[R-1][C-1], dp_3[R-1][C-1]))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import collections


def main():
    INF = 10**30
    T = int(input())
    cases = [list(map(int, input().split())) for _ in range(T)]
    for case in cases:
        N, A, B, C, D = case
        coins = collections.defaultdict(lambda : INF)
        coins[0] = 0
        frontier = [(0, 0)]
        ans = 0
        while len(frontier) > 0:
            c, node = heapq.heappop(frontier)
            if node == N:
                ans = c
                break
            candidates = [
                (c + A, 2 * node),
                (c + B, 3 * node),
                (c + C, 5 * node),
                (c + D, node + 1),
                (c + D, node - 1)
            ]
            for cand in candidates:
                if cand[1] > 0 and cand[0] < coins[cand[1]]:
                    heapq.heappush(frontier, cand)
        print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
from collections import defaultdict


def calc(case):
    # /2, /3, /5, +-1
    N, A, B, C, D = case
    memo = defaultdict(int)
    x = N
    def dp(n):
        if n == 0:
            return 0
        elif n == 1:
            return D
        elif n == 2:
            return D + min([A, D])
        for k in [2, 3, 5]:
            for i in [0, 1]:
                if memo[n // k + i] == 0:
                    memo[n // k + i] = dp(n // k + i)
        ret = min([
            n * D, 
            A + (n % 2) * D + memo[n // 2],
            A + (2 - n % 2) * D + memo[n // 2 + 1],
            B + (n % 3) * D + memo[n // 3],
            B + (3 - n % 3) * D + memo[n // 3 + 1],
            C + (n % 5) * D + memo[n // 5],
            C + (5 - n % 5) * D + memo[n // 5 + 1]
        ])
        return ret
    return dp(N)


def main():
    T = int(input())
    cases = [list(map(int, input().split())) for _ in range(T)]
    for case in cases:
        print(calc(case))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N, A, B, C = list(map(int, input().split(' ')))
    S = [input() for _ in range(N)]
    D = {
        'AB': A + B,
        'BC': B + C,
        'AC': A + C
    }
    ans = list()
    for i, s in enumerate(S):
        if D[s] == 0:
            print('No')
            return
        if s == 'AB':
            if (D['BC'] < D['AC']) or \
                (i < N and S[i + 1] == 'BC' and D['BC'] == D['AC'] == 1):
                ans.append('B')
                D['BC'] += 1
                D['AC'] -= 1
            else:
                ans.append('A')
                D['BC'] -= 1
                D['AC'] += 1
        elif s == 'BC':
            if (D['AB'] < D['AC']) or \
                (i < N and S[i + 1] == 'AB' and D['AB'] == D['AC'] == 1):
                ans.append('B')
                D['AB'] += 1
                D['AC'] -= 1
            else:
                ans.append('C')
                D['AB'] -= 1
                D['AC'] += 1
        else:  # s == 'AC'
            if (D['AB'] < D['BC']) or \
                (i < N and S[i + 1] == 'AB' and D['AB'] == D['BC'] == 1):
                ans.append('A')
                D['AB'] += 1
                D['BC'] -= 1
            else:
                ans.append('C')
                D['AB'] -= 1
                D['BC'] += 1
    print('Yes')
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N, A, B, C = list(map(int, input().split(' ')))
    S = [input() for _ in range(N)]
    D = {
        'AB': A + B,
        'BC': B + C,
        'AC': A + C
    }
    ans = list()
    for i, s in enumerate(S):
        if D[s] == 0:
            print('No')
            return
        if s == 'AB':
            if (D['BC'] < D['AC']) or \
                (i < N - 1 and S[i + 1] == 'BC' and D['BC'] == D['AC'] == 1):
                ans.append('B')
                D['BC'] += 1
                D['AC'] -= 1
            else:
                ans.append('A')
                D['BC'] -= 1
                D['AC'] += 1
        elif s == 'BC':
            if (D['AB'] < D['AC']) or \
                (i < N - 1 and S[i + 1] == 'AB' and D['AB'] == D['AC'] == 1):
                ans.append('B')
                D['AB'] += 1
                D['AC'] -= 1
            else:
                ans.append('C')
                D['AB'] -= 1
                D['AC'] += 1
        else:  # s == 'AC'
            if (D['AB'] < D['BC']) or \
                (i < N - 1 and S[i + 1] == 'AB' and D['AB'] == D['BC'] == 1):
                ans.append('A')
                D['AB'] += 1
                D['BC'] -= 1
            else:
                ans.append('C')
                D['AB'] -= 1
                D['BC'] += 1
    print('Yes')
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
s = input()[::-1]
mod_cnt = [0] * 2019
mod_cnt[0] = 1
t = 0
d = 1
for c in s:
    t += int(c) * d
    mod_cnt[t % 2019] += 1
    d *= 10
print(sum([m * (m - 1) // 2 for m in mod_cnt]))

Fixed submission:
s = input()[::-1]
mod_cnt = [0] * 2019
mod_cnt[0] = 1
t = 0
d = 1
for c in s:
    t += int(c) * d
    t %= 2019
    mod_cnt[t] += 1
    d *= 10
    d %= 2019
print(sum([m * (m - 1) // 2 for m in mod_cnt]))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
s = input()
t_list = list(map(lambda i: int(s[-i:]) % 2019, range(1, len(s) + 1)))
t_list.append(0)
counter = Counter(t_list)
print(sum([m * (m - 1) // 2 for m in counter.values()]))

Fixed submission:
s = input()[::-1]
mod_cnt = [0] * 2019
mod_cnt[0] = 1
t = 0
d = 1
for c in s:
    t += int(c) * d
    t %= 2019
    mod_cnt[t] += 1
    d *= 10
    d %= 2019
print(sum([m * (m - 1) // 2 for m in mod_cnt]))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
s = input()
t_list = list(map(lambda i: int(s[-i:]) % 2019, range(1, len(s) + 1)))
t_list.append(0)
counter = Counter(t_list)
print(sum([m * (m - 1) // 2 for m in counter.values()]))

Fixed submission:
s = input()[::-1]
mod_cnt = [0] * 2019
mod_cnt[0] = 1
t = 0
d = 1
for c in s:
    t += int(c) * d
    t %= 2019
    mod_cnt[t] += 1
    d *= 10
    d %= 2019
print(sum([m * (m - 1) // 2 for m in mod_cnt]))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
s = input()
t_list = list()
for i in range(1, len(s) + 1):
    t_list.append(int(s[-i:]) % 2019)
t_list.append(0)
counter = Counter(t_list)
print(sum([m * (m - 1) // 2 for m in counter.values()]))

Fixed submission:
s = input()[::-1]
mod_cnt = [0] * 2019
mod_cnt[0] = 1
t = 0
d = 1
for c in s:
    t += int(c) * d
    t %= 2019
    mod_cnt[t] += 1
    d *= 10
    d %= 2019
print(sum([m * (m - 1) // 2 for m in mod_cnt]))

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
cnt = 0
for length in range(4, n + 1):
    for start_index in range(n - length + 1):
        i = int(s[start_index:(start_index+length)])
        if i % 2019 == 0:
            cnt += 1
print(cnt)

Fixed submission:
s = input()[::-1]
mod_cnt = [0] * 2019
mod_cnt[0] = 1
t = 0
d = 1
for c in s:
    t += int(c) * d
    t %= 2019
    mod_cnt[t] += 1
    d *= 10
    d %= 2019
print(sum([m * (m - 1) // 2 for m in mod_cnt]))
Buggy python submission (verdict: Time Limit Exceeded):
def pow(a, n, mod):
    if n == 0:
        return 1
    elif n == 1:
        return a % mod
    ret = 1
    if n % 2 == 1:
        v = pow(a, n // 2, mod)
        w = pow(a, n // 2 + 1, mod)
        ret *= v * w
    else:
        v = pow(a, n // 2, mod)
        ret *= v ** 2
    return ret % mod


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    n_gcds = [0 for _ in range(K + 1)]
    for g in range(K, 0, -1):
        v = pow(K // g, N, MOD)
        gg = g
        while gg + g <= K:
            gg += g
            v -= n_gcds[gg]
            v %= MOD
        n_gcds[g] = v
    ans = 0
    for g, n in enumerate(n_gcds):
        ans += g * n
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def pow(a, n, mod):
    ret = 1
    pw = a
    while n > 0:
        if n & 1 == 1:
            ret *= pw
            ret %= mod
        n >>= 1
        pw *= pw
        pw %= mod
    return ret


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    n_gcds = [0 for _ in range(K + 1)]
    for g in range(K, 0, -1):
        v = pow(K // g, N, MOD)
        gg = g
        while gg + g <= K:
            gg += g
            v -= n_gcds[gg]
            v %= MOD
        n_gcds[g] = v
    ans = 0
    for g, n in enumerate(n_gcds):
        ans += g * n
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = input()
    Q = int(input())
    reverse = False
    for _ in range(Q):
        query = input()
        if len(query) == 1:
            reverse = not reverse
        else:
            _, F, C = query.split()
            if (not reverse and F == '1') or (reverse and F == '2'):
                S = C + S
            else:
                S = S + C
    if reverse:
        S = S[::-1]
    print(S)


if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque


def main():
    S = input()
    que = deque(S)
    Q = int(input())
    reverse = False
    for _ in range(Q):
        query = input()
        if len(query) == 1:
            reverse = not reverse
        else:
            _, F, C = query.split()
            if (not reverse and F == '1') or (reverse and F == '2'):
                que.appendleft(C)
            else:
                que.append(C)
    if reverse:
        que.reverse()
    print(''.join([c for c in que]))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    INF = 10 ** 10
    H, N = list(map(int, input().split(' ')))
    magic = [list(map(int, input().split(' '))) for _ in range(N)]
    MAX_A = max(list(map(lambda x: x[0], magic)))
    dp = [INF for _ in range(MAX_A + H + 1)]
    dp[0] = 0
    for h in range(1, MAX_A + H + 1):
        for i in range(N):
            a, b = magic[i]
            if h - a < 0:
                continue
            dp[h] = min(dp[h], b + dp[h - a])
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    INF = 10 ** 10
    H, N = list(map(int, input().split(' ')))
    magic = [list(map(int, input().split(' '))) for _ in range(N)]
    MAX_A = max(list(map(lambda x: x[0], magic)))
    dp = [INF for _ in range(MAX_A + H + 1)]
    dp[0] = 0
    for h in range(1, MAX_A + H + 1):
        for i in range(N):
            a, b = magic[i]
            if h - a < 0:
                continue
            dp[h] = min(dp[h], b + dp[h - a])
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    INF = 10 ** 10
    H, N = list(map(int, input().split(' ')))
    magic = [list(map(int, input().split(' '))) for _ in range(N)]
    memo = [[INF for _ in range(N)] for _ in range(H + 1)]

    def dfs(h, i=None):
        if h <= 0:
            return 0
        if i is not None and memo[h][i] < INF:
            return memo[h][i]
        ret = INF
        for j in range(N):
            a, b = magic[j]
            ret = min(ret, b + dfs(h - a, j))
        if i is not None:
            memo[h][i] = ret
        return ret

    print(dfs(H))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    INF = 10 ** 10
    H, N = list(map(int, input().split(' ')))
    magic = [list(map(int, input().split(' '))) for _ in range(N)]
    MAX_A = max(list(map(lambda x: x[0], magic)))
    dp = [INF for _ in range(MAX_A + H + 1)]
    dp[0] = 0
    for h in range(1, MAX_A + H + 1):
        for i in range(N):
            a, b = magic[i]
            if h - a < 0:
                continue
            dp[h] = min(dp[h], b + dp[h - a])
    print(min(dp[H:]))


if __name__ == '__main__':
    main()