Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
G = [0 for i in range(N)]
for i in range(N):
    A, B = map(int, input().split())
    koritu = A / B
    G[i] = (koritu, A, B)
G.sort(reverse = True)
#print(G)
dp = [[0 for i in range(H+1)] for j in range(N)]
k, a, b = G[0]
for i in range(1, H + 1):
    dp[0][i] = ((i - 1) // a + 1) * b
for j in range(1, N):
    k, a, b = G[j]
    for i in range(1, H+1):
        if i >= a:
            dp[j][i] = min(dp[j-1][i], dp[j][i-a] + b)
        else:
            dp[j][i] = min(dp[j-1][i],b)
print(dp[N-1][H])



Fixed submission:
H, N = map(int, input().split())
G = [0 for i in range(N)]
for i in range(N):
    A, B = map(int, input().split())
    koritu = A / B
    G[i] = (koritu, A, B)
G.sort(reverse = True)
#print(G)
dp = [[0 for i in range(H+1)] for j in range(N)]
k, a, b = G[0]
for i in range(1, H + 1):
    dp[0][i] = ((i - 1) // a + 1) * b
for j in range(1, N):
    k, a, b = G[j]
    for i in range(1, H+1):
        if i >= a:
            dp[j][i] = min(dp[j-1][i], dp[j][i-a] + b)
        else:
            dp[j][i] = min(dp[j-1][i],b)
print(dp[N-1][H])

Buggy python submission (verdict: Runtime Error):
H, N = map(int, input().split())
G = [0 for i in range(N)]
for i in range(N):
    A, B = map(int, input().split())
    koritu = A / B
    G[i] = (koritu, A, B)
G.sort(reverse = True)
#print(G)
dp = [[0 for i in range(H+1)] for j in range(N)]
for i in range(1, H + 1):
    dp[0][i] = ((i - 1) // a + 1) * b
for j in range(1, N):
    k, a, b = G[j]
    for i in range(1, H+1):
        if i >= a:
            dp[j][i] = min(dp[j-1][i], dp[j][i-a] + b)
        else:
            dp[j][i] = min(dp[j-1][i],b)
print(dp[N-1][H])



Fixed submission:
H, N = map(int, input().split())
G = [0 for i in range(N)]
for i in range(N):
    A, B = map(int, input().split())
    koritu = A / B
    G[i] = (koritu, A, B)
G.sort(reverse = True)
#print(G)
dp = [[0 for i in range(H+1)] for j in range(N)]
k, a, b = G[0]
for i in range(1, H + 1):
    dp[0][i] = ((i - 1) // a + 1) * b
for j in range(1, N):
    k, a, b = G[j]
    for i in range(1, H+1):
        if i >= a:
            dp[j][i] = min(dp[j-1][i], dp[j][i-a] + b)
        else:
            dp[j][i] = min(dp[j-1][i],b)
print(dp[N-1][H])

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
G = [0 for i in range(N)]
for i in range(N):
    A, B = map(int, input().split())
    koritu = A / B
    G[i] = (koritu, A, B)
G.sort(reverse = True)
#print(G)
dp = [[0 for i in range(H+1)] for j in range(N)]
for j in range(N):
    k, a, b = G[j]
    if j == 0:
        for i in range(1,H+1):
            dp[j][i] = ((i-1)//a+1) * b
    else:
        for i in range(1, H+1):
            if i >= a:
                dp[j][i] = min(dp[j-1][i], dp[j][i-a] + b)
            else:
                dp[j][i] = min(dp[j-1][i],b)
print(dp[N-1][H])



Fixed submission:
H, N = map(int, input().split())
G = [0 for i in range(N)]
for i in range(N):
    A, B = map(int, input().split())
    koritu = A / B
    G[i] = (koritu, A, B)
G.sort(reverse = True)
#print(G)
dp = [[0 for i in range(H+1)] for j in range(N)]
k, a, b = G[0]
for i in range(1, H + 1):
    dp[0][i] = ((i - 1) // a + 1) * b
for j in range(1, N):
    k, a, b = G[j]
    for i in range(1, H+1):
        if i >= a:
            dp[j][i] = min(dp[j-1][i], dp[j][i-a] + b)
        else:
            dp[j][i] = min(dp[j-1][i],b)
print(dp[N-1][H])