Buggy python submission (verdict: Time Limit Exceeded):
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = []
for i in range(N):
    A, B = map(int, input().split())
    AB.append((A, B))
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Fixed submission:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Fixed submission:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
INF = 2**60 # 無限大を表す値
def main():
    H, N = map(int, input().split())
    AB = [map(int, input().split()) for i in range(N)]
    dp = [INF] * (H + 1)
    dp[0] = 0
    for (A, B) in AB:
        for j in range(H+1):
            dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
    print(dp[H])
main()

Fixed submission:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for (A, B) in AB:
    for j in range(H+1):
        k = j - A
        if k < 0:
            k = 0
        dp[j] = min(dp[j], dp[k] + B)
print(dp[H])

Fixed submission:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
INF = 10**10 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for (A, B) in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Fixed submission:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for (A, B) in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Fixed submission:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for (A, B) in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Fixed submission:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
W = H + max(A for (A, B) in AB)
dp = [INF] * (W + 1)
dp[0] = 0
for (A, B) in AB:
    for j in range(A, W+1):
        dp[j] = min(dp[j], dp[j-A] + B)
print(min(dp[H:]))

Fixed submission:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
W = H + max(A for (A, B) in AB)
dp = [INF] * (W + 1)
dp[0] = 0
for i, (A, B) in enumerate(AB):
    for j in range(A, W+1):
        dp[j] = min(dp[j], dp[j-A] + B)
print(min(dp[H:]))

Fixed submission:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
W = H + max(A for (A, B) in AB)
dp = np.full(W+1, INF, dtype = np.int64)
dp[0] = 0
for i, (A, B) in enumerate(AB):
    for j in range(A, W+1):
        dp[j] = np.minimum(dp[j], dp[j-A] + B)
print(np.min(dp[H:]))

Fixed submission:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
W = H + max(A for (A, B) in AB)
dp = np.full((N+1, W+1), INF, dtype = np.int64)
dp[0][0] = 0
for i, (A, B) in enumerate(AB):
    dp[i+1] = np.minimum(dp[i+1], dp[i])
    for j in range(A, W+1):
        dp[i+1][j] = np.minimum(dp[i+1][j], dp[i+1][j-A] + B)
print(np.min(dp[N][H:W+1]))

Fixed submission:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
W = H + max(A for (A, B) in AB)
dp = np.full((N+1, W+1), INF, dtype = np.int64)
dp[0][0] = 0
for i, (A, B) in enumerate(AB):
    for j in range(W+1):
        dp[i+1][j] = np.minimum(dp[i+1][j], dp[i][j])
        if j-A >= 0:
            dp[i+1][j] = np.minimum(dp[i+1][j], dp[i+1][j-A] + B)
print(np.min(dp[N][H:W+1]))

Fixed submission:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])