Buggy python submission (verdict: Time Limit Exceeded):
import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [[float('inf') for _ in range(H + max(AB)[0] + 1)] for _ in range(N + 1)]
dp[0][0] = 0
for n in range(N):
    for h in range(H + max(AB)[0] + 1):
        if h - AB[n][0] >= 0:
            dp[n + 1][h] = min(dp[n + 1][h - AB[n][0]] + AB[n][1], dp[n][h])
        else:
            dp[n + 1][h] = dp[n][h]

print(min(dp[N][H:]))


Fixed submission:
import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [[float('inf') for _ in range(H + max(AB)[0] + 1)] for _ in range(N + 1)]
dp[0][0] = 0
for n in range(N):
    for h in range(H + max(AB)[0] + 1):
        if h - AB[n][0] >= 0:
            dp[n + 1][h] = min(dp[n + 1][h - AB[n][0]] + AB[n][1], dp[n][h])
        else:
            dp[n + 1][h] = dp[n][h]

print(min(dp[N][H:]))


Fixed submission:
import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])

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

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

dp = [[float('inf') for _ in range(H + max(AB)[0] + 1)] for _ in range(N + 1)]
dp[0][0] = 0
for n in range(N):
    for h in range(H + max(AB)[0] + 1):
        if h - AB[n][0] >= 0:
            dp[n + 1][h] = min(dp[n + 1][h - AB[n][0]] + AB[n][1], dp[n][h])
        else:
            dp[n + 1][h] = dp[n][h]

print(min(dp[N][H:]))


Fixed submission:
import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])

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

H, N = map(int, input().split())
magics = defaultdict(int)

for _ in range(N):
    a, b = map(int, input().split())
    for i in range(1, H // a + 2):
        if b * i < magics[a * i] or magics[a * i] == 0:
            magics[a * i] = b * i

M = len(magics)

dp = [float('inf') for _ in range(H + 1)]
dp[0] = 0

for h in range(H + 1):
    for a, b in magics.items():
        dp[h] = min(dp[h], dp[max(h - a, 0)] + b)

print(dp[H])


Fixed submission:
import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])

Buggy python submission (verdict: Runtime Error):
H, N = map(int, input().split())
tmp_magics = [float('inf') for _ in range(2 * H)]

for _ in range(N):
    a, b = map(int, input().split())
    for i in range(1, H // a + 2):
        if b * i < tmp_magics[a * i]:
            tmp_magics[a * i] = b * i

magics = []
max_magic = -float('inf')
for a, b in enumerate(tmp_magics):
    if b != float('inf'):
        magics.append([a, b])
        max_magic = max(max_magic, a)

M = len(magics)

dp = [float('inf') for _ in range(H + 1)]
dp[0] = 0

for h in range(H + 1):
    for a, b in magics:
        dp[h] = min(dp[h], dp[max(h - a, 0)] + b)

print(dp[-1])


Fixed submission:
import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])

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

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H+1)]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])


Fixed submission:
import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

magics = {}
for a, b in AB:
    for i in range(H // a + 2):
        if min(i * a, H) not in magics:
            magics[min(i * a, H)] = i * b
        else:
            magics[min(i * a, H)] = min(magics[min(i * a, H)], i * b)

sorted_keys = sorted(magics.keys())
dp = [float('inf') for _ in range(H+1)]

for key in sorted_keys:
    dp[key] = min(dp[key], magics[key])

for h in range(H):
    for key in sorted_keys:
        dp[min(h + key, H)] = min(dp[min(h + key, H)], dp[h] + magics[key])

print(dp[-1])


Fixed submission:
import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [float('inf') for _ in range(H+1)]

for i, ab in enumerate(AB):
    a, b = ab
    for j in range(H // AB[i][0] + 2):
        dp[min(AB[i][0] * j, H)] = min(dp[min(AB[i][0] * j, H)], AB[i][1] * j)
        j += 1

for h in range(H):
    for n in range(N):
        for j in range((H - h) // AB[n][0] + 2):
            dp[min(h + AB[n][0] * j, H)] = min(dp[min(h + AB[n][0] * j, H)], dp[h] + AB[n][1] * j)
print(dp[-1])

Fixed submission:
import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [float('inf') for _ in range(H+1)]

for i, ab in enumerate(AB):
    a, b = ab
    for j in range(H // AB[i][0] + 2):
        dp[min(AB[i][0] * j, H)] = min(dp[min(AB[i][0] * j, H)], AB[i][1] * j)
        j += 1

for h in range(H):
    for n in range(N):
        for j in range((H - h) // AB[n][0] + 2):
            dp[min(h + AB[n][0] * j, H)] = min(dp[min(h + AB[n][0] * j, H)], dp[h] + AB[n][1] * j)
print(dp[-1])

Fixed submission:
import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])