Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
h,n = map(int,readline().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,readline().split())
#  dp[i] i 以上の攻撃力を与えるための最小魔力
#b,a = zip(*sorted(zip(b,a))) #魔力でソート
dp = [0]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp[i] = 10**12
    for j in range(n):#すべての種類の魔法に対してループ
        if i -a[j] >= 0:#魔法が使えるなら
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
        else: dp[i] = min(dp[i],b[j])
"""print(dp)
print(a,b)"""
print(dp[h])


Fixed submission:
#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
#  dp[i] i 以上の攻撃力を与えるための最小魔力
b,a = zip(*sorted(zip(b,a))) #魔力でソート
dp = [0]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp[i] = 10**12
    for j in range(n):#すべての種類の魔法に対してループ
        if i -a[j] >= 0:#魔法が使えるなら
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
        else: dp[i] = min(dp[i],b[j])
"""print(dp)
print(a,b)"""
print(dp[h])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
#  dp[i] i 以上の攻撃力を与えるための最小魔力
b,a = zip(*sorted(zip(b,a))) #魔力でソート
dp = [0]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp[i] = 10**12
    for j in range(n):#すべての種類の魔法に対してループ
        if i -a[j] >= 0:#魔法が使えるなら
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
        else: dp[i] = min(dp[i],b[j])
"""print(dp)
print(a,b)"""
print(dp[h])


Fixed submission:
#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
#  dp[i] i 以上の攻撃力を与えるための最小魔力
b,a = zip(*sorted(zip(b,a))) #魔力でソート
dp = [0]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp[i] = 10**12
    for j in range(n):#すべての種類の魔法に対してループ
        if i -a[j] >= 0:#魔法が使えるなら
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
        else: dp[i] = min(dp[i],b[j])
"""print(dp)
print(a,b)"""
print(dp[h])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
# DP　使う魔力がk以下 の時の最大攻撃力で漸化式を立てる
# dp[i] = max(dp[i-a[j]]+b[j]) # i-a[j] >= 0となる全てのa[j]に対して
max_magic = b[0]*((h-1)//a[0]+1)
#print(max_magic)
dp = [0]*(max_magic+6)
dp[0] = 0
ans = 0
for i in range(1,max_magic+5):
    dp[i] = dp[i-1] #上書きされない時、それ以下の魔力で与えられた攻撃はいける
    for j in range(n):#すべての種類の魔法に対してループ
        if i -b[j] >= 0:#魔法が使えるなら
            dp[i] = max(dp[i],dp[i-b[j]]+a[j])
    #print(i,dp[i])
    if dp[i] >= h:
        ans = i
        print(ans)
        exit(0)


Fixed submission:
#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
#  dp[i] i 以上の攻撃力を与えるための最小魔力
b,a = zip(*sorted(zip(b,a))) #魔力でソート
dp = [0]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp[i] = 10**12
    for j in range(n):#すべての種類の魔法に対してループ
        if i -a[j] >= 0:#魔法が使えるなら
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
        else: dp[i] = min(dp[i],b[j])
"""print(dp)
print(a,b)"""
print(dp[h])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
# DP　使う魔力がk以下 の時の最大攻撃力で漸化式を立てる
# dp[i] = max(dp[i-a[j]]+b[j]) # i-a[j] >= 0となる全てのa[j]に対して
max_magic = b[0]*((h-1)//a[0]+1)
#print(max_magic)
dp = [0]*(max_magic+6)
dp[0] = 0
ans = 0
for i in range(1,max_magic+5):
    dp[i] = dp[i-1] #上書きされない時、それ以下の魔力で与えられた攻撃はいける
    for j in range(n):#すべての種類の魔法に対してループ
        if i -b[j] >= 0:#魔法が使えるなら
            dp[i] = max(dp[i],dp[i-b[j]]+a[j])
    #print(i,dp[i])
    if dp[i] >= h:
        ans = i
        print(ans)
        exit(0)


Fixed submission:
#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
#  dp[i] i 以上の攻撃力を与えるための最小魔力
b,a = zip(*sorted(zip(b,a))) #魔力でソート
dp = [0]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp[i] = 10**12
    for j in range(n):#すべての種類の魔法に対してループ
        if i -a[j] >= 0:#魔法が使えるなら
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
        else: dp[i] = min(dp[i],b[j])
"""print(dp)
print(a,b)"""
print(dp[h])