Buggy python submission (verdict: Runtime Error):
INF = 1145141919810893
H,N = map(int,input().split())
A=[]
B=[]
memo = [INF]*20000
def HP(K):
    if K<=0:
        return 0
    if memo[K]!=INF:
        return memo[K]
    R=INF
    for i in range(N):
        r = B[i]+HP(K-A[i])
        R=min(R,r)
    memo[K]=R
    return R

for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
print(HP(H))



Fixed submission:
INF = 1145141919810893

H,N = map(int,input().split())
A=[]
B=[]
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

#dp[i]=体力がちょうどiのモンスターを倒すのに必要な魔力の最小値
#もしそのような魔力が存在しない場合、INF
#INFは10^9くらいあれば足りると思う(適当)
dp = [INF]*20000
dp[0]=0
#体力が0のモンスターを倒すのに必要な魔力は0
#iは小さい順に決定することができる
#なぜなら、i<jのとき決定したdp[j]の値はdp[i]に影響しないから
for i in range(H):
    #dp[H]から配る遷移は、必ずdp[H]より大きい値を配ることになるので、不要
    #よってH-1までやればOK
    #dp[i]の値はこの時点で確定する
    if dp[i]==INF:
        continue
    for j in range(N):
        #いわゆる配るDP
        dp[i+A[j]]=min(dp[i+A[j]],dp[i]+B[j])

#これで答えはdp[H]であるかというと、そうとは限らない
#なぜなら、dp[H+1]に行くコストがdp[H]に行くコストより安いかもしれないから
#今回は「与えるダメージがH以上」で条件を達成することができる
#なので、H以上のdpについて精査して、最もコストが低いものが答えである
Ans=INF
for d in dp[H:]:
    Ans=min(Ans,d)
print(Ans)

Buggy python submission (verdict: Runtime Error):
INF = 1145141919810893
memo = [INF]*20000
def HP(K):
    if K<=0:
        return 0
    if memo[K]!=INF:
        return memo[K]
    R=INF
    for i in range(N):
        r = B[i]+HP(K-A[i])
        R=min(R,r)
    memo[K]=R
    return R

H,N = map(int,input().split())
A=[]
B=[]
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
print(HP(H))



Fixed submission:
INF = 1145141919810893

H,N = map(int,input().split())
A=[]
B=[]
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

#dp[i]=体力がちょうどiのモンスターを倒すのに必要な魔力の最小値
#もしそのような魔力が存在しない場合、INF
#INFは10^9くらいあれば足りると思う(適当)
dp = [INF]*20000
dp[0]=0
#体力が0のモンスターを倒すのに必要な魔力は0
#iは小さい順に決定することができる
#なぜなら、i<jのとき決定したdp[j]の値はdp[i]に影響しないから
for i in range(H):
    #dp[H]から配る遷移は、必ずdp[H]より大きい値を配ることになるので、不要
    #よってH-1までやればOK
    #dp[i]の値はこの時点で確定する
    if dp[i]==INF:
        continue
    for j in range(N):
        #いわゆる配るDP
        dp[i+A[j]]=min(dp[i+A[j]],dp[i]+B[j])

#これで答えはdp[H]であるかというと、そうとは限らない
#なぜなら、dp[H+1]に行くコストがdp[H]に行くコストより安いかもしれないから
#今回は「与えるダメージがH以上」で条件を達成することができる
#なので、H以上のdpについて精査して、最もコストが低いものが答えである
Ans=INF
for d in dp[H:]:
    Ans=min(Ans,d)
print(Ans)

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1145141919810893

H,N = map(int,input().split())
A=[]
B=[]
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

#dp[i]=体力がちょうどiのモンスターを倒すのに必要な魔力の最小値
#もしそのような魔力が存在しない場合、INF
#INFは10^9くらいあれば足りると思う(適当)
dp = [INF]*20000
dp[0]=0
#体力が0のモンスターを倒すのに必要な魔力は0
#iは小さい順に決定することができる
#なぜなら、i<jのとき決定したdp[j]の値はdp[i]に影響しないから
for i in range(H):
    #dp[H]から配る遷移は、必ずdp[H]より大きい値を配ることになるので、不要
    #よってH-1までやればOK
    #dp[i]の値はこの時点で確定する
    if dp[i]==INF:
        continue
    for j in range(N):
        #いわゆる配るDP
        dp[i+A[j]]=min(dp[i+A[j]],dp[i]+B[j])

#これで答えはdp[H]であるかというと、そうとは限らない
#なぜなら、dp[H+1]に行くコストがdp[H]に行くコストより安いかもしれないから
#今回は「与えるダメージがH以上」で条件を達成することができる
#なので、H以上のdpについて精査して、最もコストが低いものが答えである
Ans=INF
for d in dp[H:]:
    Ans=min(Ans,d)
print(Ans)





Fixed submission:
INF = 1145141919810893

H,N = map(int,input().split())
A=[]
B=[]
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

#dp[i]=体力がちょうどiのモンスターを倒すのに必要な魔力の最小値
#もしそのような魔力が存在しない場合、INF
#INFは10^9くらいあれば足りると思う(適当)
dp = [INF]*20000
dp[0]=0
#体力が0のモンスターを倒すのに必要な魔力は0
#iは小さい順に決定することができる
#なぜなら、i<jのとき決定したdp[j]の値はdp[i]に影響しないから
for i in range(H):
    #dp[H]から配る遷移は、必ずdp[H]より大きい値を配ることになるので、不要
    #よってH-1までやればOK
    #dp[i]の値はこの時点で確定する
    if dp[i]==INF:
        continue
    for j in range(N):
        #いわゆる配るDP
        dp[i+A[j]]=min(dp[i+A[j]],dp[i]+B[j])

#これで答えはdp[H]であるかというと、そうとは限らない
#なぜなら、dp[H+1]に行くコストがdp[H]に行くコストより安いかもしれないから
#今回は「与えるダメージがH以上」で条件を達成することができる
#なので、H以上のdpについて精査して、最もコストが低いものが答えである
Ans=INF
for d in dp[H:]:
    Ans=min(Ans,d)
print(Ans)