Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))
    DP = [INF] * (H+1)
    DP[0] = 0
    for h in range(1, H+1):
        for i in range(N):
            DP[h] = min(DP[h], (DP[h-AB[i][0]]+AB[i][1] if h-AB[i][0]>0 else AB[i][1]))

    print(DP[-1])

main()


Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))
    DP = [INF] * (H+1)
    DP[0] = 0
    for h in range(1, H+1):
        for i in range(N):
            DP[h] = min(DP[h], (DP[h-AB[i][0]]+AB[i][1] if h-AB[i][0]>0 else AB[i][1]))

    print(DP[-1])

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = [lmis() for _ in range(N)]
    @lru_cache(maxsize=None)
    def rec(h):
        if h <= 0:
            return 0
        return min(rec(h-a)+b for a, b in AB)
    print(rec(H))

main()


Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))
    DP = [INF] * (H+1)
    DP[0] = 0
    for h in range(1, H+1):
        for i in range(N):
            DP[h] = min(DP[h], (DP[h-AB[i][0]]+AB[i][1] if h-AB[i][0]>0 else AB[i][1]))

    print(DP[-1])

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))

    @lru_cache(maxsize=10000)
    def rec(h):
        if h <= 0:
            return 0
        return min(rec(h - a) + b for a, b in AB)

    print(rec(H))

main()


Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))
    DP = [INF] * (H+1)
    DP[0] = 0
    for h in range(1, H+1):
        for i in range(N):
            DP[h] = min(DP[h], (DP[h-AB[i][0]]+AB[i][1] if h-AB[i][0]>0 else AB[i][1]))

    print(DP[-1])

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))
    d = defaultdict(int)
    for h in range(H):
        for i in range(N):
            p_use = d[(h-AB[i][0], i)]+AB[i][1] if h-AB[i][0] >= 0 else AB[i][1]
            p_not = d[(h,i-1)] if i>0 else INF
            d[(h,i)] = min(p_use,p_not)
    print(d[(H-1, N-1)])

main()


Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))
    DP = [INF] * (H+1)
    DP[0] = 0
    for h in range(1, H+1):
        for i in range(N):
            DP[h] = min(DP[h], (DP[h-AB[i][0]]+AB[i][1] if h-AB[i][0]>0 else AB[i][1]))

    print(DP[-1])

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))
    d = defaultdict(int)
    for h in range(H):
        for i in range(N):
            p_use = d[(h-AB[i][0], i)]+AB[i][1] if h-AB[i][0] >= 0 else AB[i][1]
            p_not = d[(h,i-1)] if i>0 else INF
            d[(h,i)] = min(p_use,p_not)
    print(d[(H-1, N-1)])

main()


Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))
    DP = [INF] * (H+1)
    DP[0] = 0
    for h in range(1, H+1):
        for i in range(N):
            DP[h] = min(DP[h], (DP[h-AB[i][0]]+AB[i][1] if h-AB[i][0]>0 else AB[i][1]))

    print(DP[-1])

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))

    @lru_cache(maxsize=10000)
    def rec(h):
        if h <= 0:
            return 0
        return min(rec(h - a) + b for a, b in AB)

    print(rec(H))

main()


Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))
    DP = [INF] * (H+1)
    DP[0] = 0
    for h in range(1, H+1):
        for i in range(N):
            DP[h] = min(DP[h], (DP[h-AB[i][0]]+AB[i][1] if h-AB[i][0]>0 else AB[i][1]))

    print(DP[-1])

main()