Problem:
 Score : 500 points    Problem Statement Ibis is fighting with a monster.  The health of the monster is H .  Ibis can cast N kinds of spells. Casting the i -th spell decreases the monster's health by A_i , at the cost of B_i Magic Points.  The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.  Ibis wins when the health of the monster becomes 0 or below.  Find the minimum total Magic Points that have to be consumed before winning.      Constraints  1 \leq H \leq 10^4  1 \leq N \leq 10^3  1 \leq A_i \leq 10^4  1 \leq B_i \leq 10^4  All values in input are integers.         Input Input is given from Standard Input in the following format:  H  N  A_1  B_1  :  A_N  B_N       Output Print the minimum total Magic Points that have to be consumed before winning.        Sample Input 1 9 3
8 3
4 2
2 1      Sample Output 1 4  First, let us cast the first spell to decrease the monster's health by 8 , at the cost of 3 Magic Points. The monster's health is now 1 .  Then, cast the third spell to decrease the monster's health by 2 , at the cost of 1 Magic Point. The monster's health is now -1 .  In this way, we can win at the total cost of 4 Magic Points.       Sample Input 2 100 6
1 1
2 3
3 9
4 27
5 81
6 243      Sample Output 2 100  It is optimal to cast the first spell 100 times.       Sample Input 3 9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461      Sample Output 3 139815

Solution (Python):



def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)

    h, n = map(int, input().split())
    maho = []
    for _ in range(n):
        maho.append(list(map(int, input().split())))

    
    

    dp = [[10 ** 12] * (h + 1) for _ in range(3)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(h + 1):
            if j == 0:
                dp[(i + 1) % 3][0] = 0
            dp[(i + 1) % 3][j] = min(dp[i % 3][j],
                                     dp[(i + 1) % 3][max(0, j - maho[i][0])] + maho[i][1])
    print(dp[n % 3][h])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    H, N = map(int, input().split())
    AB = sorted([tuple(map(int, input().split())) for _ in range(N)])
    v = [0] * (H + 1)
    for i in range(1, H + 1):
        v[i] = min(v[max(i - a, 0)] + b for a, b in AB)
    print(v[-1])

main()

Solution (Python):
def main():

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

    dp = [float('inf') for _ in range(H+1)]
    dp[0] = 0
    for i in range(0, H):
        if dp[i] != float('inf'):
            for j in range(N):
                if AB[j][0] + i >= H:
                    dp[H] = min(dp[H], dp[i]+AB[j][1])
                else:
                    dp[AB[j][0]+i] = min(dp[AB[j][0]+i], dp[i] + AB[j][1])
    if dp[H] == float('inf'):
        return -1
    return dp[H]

if __name__ == '__main__':
    print(main())

Solution (Python):
h, n = map(int,input().split())
maho = []
for i in range(n):
    aa,ba = map(int,input().split())
    maho.append([aa,ba])

dp = [0 for i in range(h+1)]


for i in range(1,h+1):
    cost = 10000000000
    for j in range(n):
        if i - maho[j][0] < 0:
            cost = min(cost, maho[j][1])
        else:
            cost = min(cost, dp[i-maho[j][0]] + maho[j][1])

    dp[i] = cost


print(dp[h])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from copy import deepcopy
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


h, n = LI()
A = []
B = []
for _ in range(n):
    a, b = LI()
    A += [a]
    B += [b]


dp = [INF] * (h + 1)
dp[0] = 0
for i in range(n):
    for j in range(h):
        dp[min(h, j + A[i])] = min(dp[min(j + A[i], h)], dp[j] + B[i])


print(dp[-1])

Solution (Python):
import sys
input = sys.stdin.readline
H, N = [int(x) for x in input().split()]
AB = []
for _ in range(N):
    AB.append([int(x) for x in input().split()])
AB = sorted(AB)
A = []
B = []
for i in range(N):
    A.append(AB[i][0])
    B.append(AB[i][1])
dp = [10 ** 10] * 10001
dp[0] = 0
for i in range(1, H + 1):
    dp_ = 10 ** 10
    for j in range(N):
        if i - A[j] >= 0:
            dp_ = min(dp_, dp[i - A[j]] + B[j])
        else:
            dp_ = min(dp_, B[j])
    dp[i] = dp_
print(dp[H])

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    h, n = LI()
    a_s = []
    b_s = []

    for i in range(n):
        a, b = LI()
        a_s.append(a)
        b_s.append(b)

    dp = [INF for j in range(h+1)]
    dp[0] = 0
    for i in range(h):
        for j in range(n):
            if i + a_s[j] > h:
                if dp[h] > dp[i] + b_s[j]:
                    dp[h] = dp[i] + b_s[j]
            else:
                if dp[i + a_s[j]] > dp[i] + b_s[j]:
                    dp[i + a_s[j]] = dp[i] + b_s[j]

    print(dp[h])

if __name__ == '__main__':
    main()

Solution (Python):
H, N = [int(s) for s in input().split()]
dec = []
cost = []
for i in range(N):
    a, b = [int(s) for s in input().split()]
    dec.append(a)
    cost.append(b)
bar = ((H-1)//dec[0]+1)*cost[0]
memo = [bar]*(H+1)
memo[0] = 0
for h in range(1,H+1):
    for i in range(N):
        memo[h] = min(memo[h], memo[max(0,h-dec[i])]+cost[i])
print(memo[H])

Solution (Python):
h, n = [int(s) for s in input().strip().split()]
A, B = [], []
for _ in range(n):
    a, b = [int(s) for s in input().strip().split()]
    A.append(a)
    B.append(b)

dp = [0] + [float("inf")] * h
for a, b in zip(A, B):
    for i in range(1, h + 1):
        dp[i] = min(dp[i], b + dp[max(i - a, 0)])
print(dp[-1])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,n = LI()
    g = LIR(n)
    dp = [float("inf")]*(h+1)
    dp[h] = 0
    for a,b in g:
        for i in range(h+1)[::-1]:
            ni = max(0,i-a)
            nd = dp[i]+b
            if nd < dp[ni]:
                dp[ni] = nd
    print(dp[0])
    return


if __name__ == "__main__":
    solve()

Solution (Python):
h, n = map(int, input().split())
a, b = [], []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)

lst = [10**9 for i in range(h+1)]
lst[0] = 0

for i in range(1, h+1):
    for j in range(n):
        if i-a[j] > 0:
            lst[i] = min(lst[i], lst[i-a[j]]+b[j])
        else:
            if a[j] >= i:
                lst[i] = min(lst[i], b[j])

print(lst[-1])

Solution (Python):
h, n  = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]

dp = [10**10] * (h+1)
dp[0] = 0

for i in range(1,h+1):
    for j in range(n):
        if(i >= ab[j][0]):
            dp[i] = min(dp[i], dp[ i - ab[j][0]]+ ab[j][1])
        else:
            dp[i] = min(dp[i], dp[0] + ab[j][1])

print(dp[h])

Solution (Python):
import sys
import fractions
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H, N = IL()
ab = [IL() for i in range(N)]

dp = [MAX_INT for i in range(H+1)]
dp[H] = 0
for hp in range(H+1)[::-1]:
  if dp[hp] == MAX_INT:
    continue
  for at,mp in ab:
    dp[max(0,hp - at)] = min(dp[max(0,hp - at)], dp[hp] + mp)
print(dp[0])

Solution (Python):
def main():
    h, n = map(int, raw_input().split())
    ab = []
    for _ in xrange(n):
        a, b = map(int, raw_input().split())
        ab.append([a, b])
    dp = [float('inf')] * (h + 1)
    dp[0] = 0
    for i in range(1, h + 1):
        for a, b in ab:
            dp[i] = min(dp[i], b + dp[max(0, i - a)])
    print dp[-1]

main()

Solution (Python):
h,n=map(int,input().split())
a=[]
b=[]
for _ in range(n):
    i,j = map(int,input().split())
    a.append(i)
    b.append(j)

dp=[float("inf") for _ in range(h+1)]
dp[0]=0
for i in range(h+1):
    for j in range(n):
        if i-a[j]<=0:
            dp[i] = min(dp[i],dp[0]+b[j])
        else:
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
print(dp[-1])

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

H,N=LI()
DP=[10**15]*(H+1)
DP[H] = 0
waza = [LI() for i in range(N)]

for i in range(N):
    for h in range(1, H+1)[::-1]:
        DP[max(0, h - waza[i][0])] = min(DP[max(0, h - waza[i][0])], DP[h] + waza[i][1])
print(DP[0])

Solution (Python):
import sys
input = sys.stdin.readline

H, N = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
INF = 10**10
dp = [INF] * (H+1)
dp[0] = 0
for i in range(N):
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(0, j-A[i])]+B[i])
print(dp[H])

Solution (Python):
def main():
    import sys

    input = sys.stdin.readline

    inf = 10 ** 8 + 10

    h, n = map(int, input().split())
    *ab, = (list(map(int, input().split())) for _ in range(n))

    dp = [[inf] * (h + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    

    for i, (a, b) in enumerate(ab):
        for hp in range(h + 1):
            if hp < a:
                dp[i + 1][hp] = min(dp[i][hp], dp[i + 1][0] + b)
            else:
                dp[i + 1][hp] = min(dp[i][hp], dp[i + 1][hp - a] + b)

    print(dp[n][h])


if __name__ == '__main__':
    main()

Solution (Python):
inpl = lambda: list(map(int,input().split()))
H, N = inpl()
A = []
B = []
for _ in range(N):
    a, b = inpl()
    A.append(a)
    B.append(b)

Max = 10**9
dp = [Max] * (H+1)
dp[0] = 0
for h in range(H):
    if dp[h] >= Max:
        continue
    for n in range(N):
        k = h + A[n]
        if k > H:
            k = H
        dp[k] = min(dp[h]+B[n], dp[k])
print(dp[H])

Solution (Python):
H, N = map(int, input().split())
dp = [[0]*(H+1) for _ in range(N)]
AB = [list(map(int, input().split())) for _ in range(N)]
a, b = AB[0]
for i in range(1, H+1):
    dp[0][i] = ((i-1)//a+1)*b
for i in range(1, N):
    a, b = AB[i]
    for j in range(H+1):
        if j>=a:
            dp[i][j] = min(dp[i][j-a]+b, dp[i-1][j])
        else:
            dp[i][j] = min(b, dp[i-1][j])
print(dp[-1][-1])

Solution (Python):
h,n,*t=map(int,open(0).read().split())
dp=[10**18]*(h+1)
dp[0]=0
for a,b in zip(*[iter(t)]*2):
    for j in range(h+1):
        dp[j]=min(dp[j],dp[max(0,j-a)]+b)
print(dp[h])

Solution (Python):
h,n=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(n)]

dp = [123456789012] * (10**8 + 10)

dp[0] = 0
for i in range(h+1):
    if dp[i] == 123456789012:
        continue
    for j in range(n):
        dp[i+ab[j][0]] = min(dp[i+ab[j][0]],dp[i] + ab[j][1])
ans = 123456789012
for i in range(h,h+10000+2):
    ans = min(ans,dp[i])
print(ans)

Solution (Python):
h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
inf = 10 ** 9
dp = [inf for _ in range(h + 1)]
dp[0] = 0

for i in range(n):
    a, b = ab[i]
    for j in range(h):
        if dp[j] < inf:
            jj = min(j + a, h)
            dp[jj] = min(dp[j] + b, dp[jj])
print(dp[-1])

Solution (Python):
h,n=[int(j) for j in input().split()]
ab=[[int(j) for j in input().split()] for i in range(n)]
dp=[10**18]*(h+1)
dp[0]=0
ans=10**18
for a,b in ab:
    for i in range(h+1):
        if dp[i]!=10**18:
            if i+a<h:
                if dp[i]+b<dp[i+a]:
                    dp[i+a]=dp[i]+b
            else:
                if dp[i]+b<ans:
                    ans=dp[i]+b

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [10**14]*(H+1)
dp[0] = 0
for a, b in AB:
    for i in range(H+1):
        if i < a:
            if dp[i] > b:
                dp[i] = b
        else:
            if dp[i] > dp[i-a]+b:
                dp[i] = dp[i-a]+b
print(dp[H])

Solution (Python):

def resolve():
    H,N=(int(i) for i in input().split())
    magics=[[int(i) for i in input().split()] for j in range(N)]
    mx=2**31
    dpt=[mx for i in range(H+1)]
    dpt[-1]=0
    for i in range(H,0,-1):
        
        current=dpt[i]
        if current> dpt[0]:
            continue
        for m in magics:
            dpt[max(0,i-m[0])]=min(dpt[max(0,i-m[0])],current+m[1])
    print(dpt[0])

if __name__ == "__main__":
    resolve()

Solution (Python):
h,n = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
dp = [10 ** 18] * (h+1)
dp[0] = 0
for i in range(h):
  for a,b in ab:
    c = min(h,i+a)
    dp[c] = min(dp[c],dp[i]+b)
ans = dp[h]
print(ans)

Solution (Python):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

h, n = map(int, input().split())
spells = [list(map(int, input().split())) for _ in range(n)]

dp = [10** 30 for _ in range(h+1)]
dp[0] = 0
for a, b in spells:
	for i in range(h):
		dp[min(i+a, h)] = min(dp[min(i+a, h)], dp[i]+b)

print(dp[h])

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


H, N = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]


dp = [INF] * (H + 1)
dp[H] = 0
for a, b in AB:
    for h in reversed(range(H + 1)):
        dp[max(0, h - a)] = min(dp[h] + b, dp[max(0, h - a)])
print(dp[0])

Solution (Python):
H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
A = [AB[i][0] for i in range(N)]
B = [AB[i][1] for i in range(N)]
dp = [10**9]*(2*10**4+1)
dp[0] = 0
for h in range(10**4+1):
    for i in range(N):
        dp[h+A[i]] = min(dp[h+A[i]],dp[h]+B[i])


ans = 10**9
for i in range(H,2*10**4+1):
    ans = min(ans,dp[i])

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H,N = map(int,readline().split())
m = map(int,read().split())
AB = zip(m,m)

INF = 10 ** 18
dp = [INF] * (20000)
dp[0] = 0

for a,b in AB:
    for n in range(H):
        if dp[n+a] > dp[n] + b:
            dp[n+a] = dp[n] + b

answer = min(dp[H:])
print(answer)

Solution (Python):
def solve(h, n, a_list, b_list):
    res = 10 ** 10
    dp = [10 ** 10] * h
    dp[0] = 0
    for i in range(h):
        for j in range(n):
            if i + a_list[j] < h:
                dp[i + a_list[j]] = min(dp[i + a_list[j]], dp[i] + b_list[j])
            else:
                res = min(res, dp[i] + b_list[j])
    return res


def main():
    h, n = map(int, input().split())
    a_list = [0] * n
    b_list = [0] * n
    for i in range(n):
        a, b = map(int, input().split())
        a_list[i] = a
        b_list[i] = b
    res = solve(h, n, a_list, b_list)
    print(res)


def test():
    assert solve(9, 3, [8, 4, 2], [3, 2, 1]) == 4
    assert solve(100, 6, [1, 2, 3, 4, 5, 6], [1, 3, 9, 27, 81, 243]) == 100
    assert solve(
        9999, 10,
        [540, 691, 700, 510, 415, 551, 587, 619, 588, 176],
        [7550, 9680, 9790, 7150, 5818, 7712, 8227, 8671, 8228, 2461]
    ) == 139815


if __name__ == "__main__":
    test()
    main()

Solution (Python):
h, n = map(int, input().split())
a = []
b = []
for i in range(n):
    ia, ib = map(int, input().split())
    a.append(ia)
    b.append(ib)

dp = [[0 for i in range(h)] for j in range(n)]

for i in range(n):
    for j in range(h):
        if i == 0:
            tmp = (j + 1) // a[i]
            if tmp != (j + 1) / a[i]:
                tmp += 1
            dp[i][j] = tmp * b[i]
        else:
            if j != 0:
                if j - a[i] < 0:
                    tmp = b[i]
                else:
                    tmp = dp[i][j - a[i]] + b[i]
                dp[i][j] = min(dp[i - 1][j], tmp)
            else:
                tmp = (j + 1) // a[i]
                if tmp != (j + 1) / a[i]:
                    tmp += 1
                dp[i][j] = min(dp[i - 1][j], tmp * b[i])

print(dp[-1][-1])

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

h,n=map(int,input().split())
AB=[tuple(map(int,input().split())) for i in range(n)]

dp=[inf]*(h+10**4+2)
dp[0]=0
for i in range(1,h+10**4+2):
    for a,b in AB:
        
        if not (0<=i-a<h+10**4+2): continue
        dp[i]=min(dp[i],dp[i-a]+b)
for i in range(h,h+10**4+2):
    mans=min(mans,dp[i])
print(mans)

Solution (Python):
h,n = map(int,input().split())
a = [0]*n
c = [0]*n
for i in range(n):
  a[i],c[i] = (map(int,input().split()))
x = [10**10 for i in range(h+1)]
x[0] = 0
for i in range(1,h+1):
  for j in range(0,n):
    if(a[j] > i):
      x[i] = min(x[i],c[j])
    else:
      x[i] = min(x[i],x[i-a[j]]+c[j])
print(x[h])

Solution (Python):
import sys

h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = [INF] * (20201)
dp[0] = 0
for line in sys.stdin:
    a, b = map(int, line.split())
    for i in range(10000):
        if dp[i] == INF:
            continue
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))

Solution (Python):
import sys
input=sys.stdin.readline
h,n=map(int,input().split())
INF=10**9
dp=[INF]*(h+1+10**4)
magic=[]
for i in range(n):
    a,b=map(int,input().split())
    magic.append((a,b))
dp[0]=0
for i in range(1,h+1+10**4):
    for j in magic:
        if i-j[0]>=0:
            if dp[i-j[0]]+j[1]<dp[i]:
                dp[i]=dp[i-j[0]]+j[1]
ans=INF
for i in range(h,h+1+10**4):
    ans=min(ans,dp[i])
print(ans)

Solution (Python):
h,n=map(int,input().split())
ab=[]
inf=float('inf')
for i in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
dp=[inf]*(h+1) 
dp[0]=0
for i in range(n):
    for j in range(h+1):
        if dp[j]!=inf:
            idx=min(j+ab[i][0],h)
            dp[idx]=min(dp[idx],dp[j]+ab[i][1])
print(dp[-1])

Solution (Python):
H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
dp = [0]+[float("inf")]*H
for i in range(N):
    for h in range(H+1):
        t = h + AB[i][0] 
        if h + AB[i][0] > H:
            t = H
        dp[t] = min(dp[t],dp[h]+AB[i][1])
print(dp[H])

Solution (Python):
import sys
input=sys.stdin.readline

def main():
    H, N = map(int, input().split())
    AB = [tuple(map(int, input().split()))for _ in range(N)]
    DP = [10**10] * (H+1)
    DP[H] = 0
    for h in range(H, 0, -1):
        for a, b in AB:
            x = max(0, h - a)
            DP[x] = min(DP[x], DP[h] + b)
    print(DP[0])

if __name__ == "__main__":
    main()

Solution (Python):
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans



h,n = list(map(int, input().split()))
waza=[]
for i in range(n):
    waza.append(list(map(int, input().split())))
    
dp = [10**10 for _ in range(h+1)]
dp[0]=0
for i in range(h):
    for j in range(n):
        dp[min(h,i+waza[j][0])] = min(dp[min(h,i+waza[j][0])], dp[i]+waza[j][1])
        
    
    
print(dp[h])

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict

INF = float("inf")
con = 10 ** 9 + 7

def getlist():
	return list(map(int, input().split()))


def main():
	H, N = getlist()
	A = []
	B = []
	for i in range(N):
		a, b = getlist()
		A.append(a)
		B.append(b)

	
	DP = [INF] * (2 * (10 ** 4) + 1)
	DP[0] = 0

	for i in range(10 ** 4):
		for j in range(N):
			a = A[j]
			DP[i + a] = min(DP[i + a], DP[i] + B[j])

	ans = INF
	for i in range(H, 10 ** 4 + 1):
		ans = min(ans, DP[i])
	print(ans)


if __name__ == '__main__':
	main()

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

h,n = get_nums_l()
lines = sys.stdin.readlines()
magics = [ tuple(map(int, l.split(" "))) for l in lines ]


dp = [99999999999999] * (h + 10)

dp[0] = 0
for i in range(len(dp)):
    for m in magics:
        next_ = min(i + m[0], h)
        tmp = dp[i] + m[1]
        if dp[next_] > tmp:
            dp[next_] = tmp

print(dp[h])

Solution (Python):
h, n = map(int, input().split())
a = []
b = []
for i in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

INF = 1e100
    
dp = [[INF] * (1+10**4) for i in range(1+10**3)]


dp[0][0] = 0

for i in range(n):
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][min(h, j+a[i])] = min(dp[i+1][min(h, j+a[i])], dp[i+1][j] + b[i])

print(dp[n][h])

Solution (Python):
h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=10**10
f=h+max(a)+1

dp=[f*[inf]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  dp[i][0]=0
  for j in range(f):
    dp[i][j]=dp[i-1][j]
    if j-a[i-1]>=0:dp[i][j]=min(dp[i][j],dp[i][j-a[i-1]]+b[i-1])
print(min(dp[-1][h:]))

Solution (Python):
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())

INF=10**9
dp=[INF]*(H+1)

dp[0]=0
for i in range(N):
  for j in range(len(dp)):
    if dp[j]!=INF:
      if j+A[i]<len(dp):
        if dp[j+A[i]]>dp[j]+B[i]:
          dp[j+A[i]]=dp[j]+B[i]
      else:
        if dp[len(dp)-1]>dp[j]+B[i]:
          dp[len(dp)-1]=dp[j]+B[i]
print(dp[-1])

Solution (Python):
H, N = map(int, input().split())
L = []
for _ in range(N):
    a, b = map(int, input().split())
    L.append((a, b))

INF = 1000000000
dp = [INF] * (H+1 + 10000)
dp[H] = 0
for h in range(H-1, -10000, -1):
    tmp = INF
    for a, b in L:
        if h + a <= H:
            c = dp[h+a] + b
            tmp = tmp if tmp < c else c
    dp[h] = tmp

print(min(dp[0], min(dp[H+1:])))

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,n = m()

a = [l() for i in range(n)]

a.sort(reverse = True)

dp = [mod for i in range(h+1)]

dp[0] = 0

for i in range(n):
    z,x = a[i]
    
    for j in range(z,h+1):
        dp[j] = min(dp[j],dp[j-z] + x)
    mi = mod
    for j in range(max(0,h-z),h+1):
        mi = min(mi,dp[j])

    dp[-1] = min(dp[-1],mi+x)
print(dp[-1])

Solution (Python):
import sys
input = sys.stdin.readline
H, N = map(int, input().split())
a = []
for _ in range(N):
  u, v = map(int, input().split())
  a.append((u, v))
dp = [float("inf")] * (H + 1)
dp[H] = 0
for i in range(N):
  for j in range(H, -1, -1):
    dp[max(j - a[i][0], 0)] = min(dp[max(j - a[i][0], 0)], dp[j] + a[i][1])
print(dp[0])

Solution (Python):
H,N=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]

INF=10**9

dp=[INF for _ in range(H+1)]
dp[H]=0
for h in range(H,0,-1):
    for n in range(N):
        A,B=AB[n]
        newH=max(0,h-A)
        dp[newH]=min(dp[newH], dp[h]+B)

print(dp[0])

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read






h,n = [int(i) for i in readline().split()]

 
def div(m,a,b,dp): 
    for i in range(m-a+1):
        dp[i+a] = min(dp[i+a], dp[i]+b)
    for i in range(max(m-a+1,0),m):
        dp[-1] = min(dp[-1],dp[i]+b)
        


INF = 10**9+7
dp =[INF]*(h+1)
dp[0] = 0

for _ in range(n):
    a,b = [int(i) for i in readline().split()]
    div(h,a,b,dp)
    
 


print(dp[-1])

Solution (Python):
h, n = [int(i) for i in input().split()]
ab = [[int(i) for i in input().split()] for _ in range(n)]
dp = [10 ** 9] * (h + 1)
dp[0]=0

for i in range(h):
    for j in ab:
        k = min(i + j[0], h)
        dp[k] = min(dp[k], dp[i] + j[1])
print(dp[-1])

Solution (Python):
h, n = map(int,input().split())
ablist=[]
hplist=[10**9]*(h+1)
hplist[0]=0
for i in range(n):
    a, b = map(int,input().split())
    ablist.append([a,b])


for i in range(n):
    now=ablist[i]
    for j in range(h+1):
        if j<=now[0]:
            hplist[j]=min(now[1], hplist[j])
        else:
            hplist[j]=min(hplist[j], hplist[j-now[0]]+now[1])

print(hplist[-1])

Solution (Python):
h, n = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

dp = [10**18] * (h + 1 + 10 ** 5)
dp[h + 10 ** 5] = 0
for i in range(n):
    a, b = info[i]
    for j in range(h + 1 + 10 ** 5)[::-1]:
        if j - a >= 0:
            dp[j - a] = min(dp[j] + b, dp[j - a])
print(min(dp[0:10**5 + 1]))

Solution (Python):
def main():
    h, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    dp = [10**10]*(h+1)
    dp[0] = 0
    for i in range(h):
        for a, b in ab:
            j = i+a
            if j > h:
                j = h
            dp[j] = min(dp[j], dp[i]+b)
    print(dp[-1])


main()

Solution (Python):
H,N = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]

INF = float('inf')
dp = [INF]*(H+1)
dp[H] = 0
for a,b in AB:
    for i in range(H,0,-1):
        if i-a <= 0:
            dp[0] = min(dp[0], dp[i]+b)
        else:
            dp[i-a] = min(dp[i-a], dp[i]+b)
print(dp[0])

Solution (Python):
INF = 10 ** 20

(h, n) = map(int, raw_input().split())

dp = [INF for i in xrange(h + 1)]
dp[0] = 0

for i in xrange(n):
    (a, b) = map(int, raw_input().split())
    for j in xrange(h + 1):
        if dp[j] >= INF:
            continue
        nxt = min(j + a, h)
        dp[nxt] = min(dp[nxt], dp[j] + b)
print dp[h]

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class RangeMinimumQuery:
    def __init__(self, n, func=min, inf=float("inf")):
        self.n0 = 2**(n-1).bit_length()
        self.op = func
        self.inf = inf
        self.data = [self.inf]*(2*self.n0)

    def construct(self, lis):
        for i, x in enumerate(lis):
            self.data[i+self.n0-1] = x
        for i in range(self.n0-2, -1, -1):
            self.data[i] = self.op(self.data[2*i+1], self.data[2*i+2])

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.inf
        while l < r:
            if r&1:
                r -= 1
                res = self.op(res, self.data[r-1])
            if l&1:
                res = self.op(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i+1:
            i = ~-i//2
            self.data[i] = self.op(self.data[2*i+1], self.data[2*i+2])

h,n = map(int, input().split())
bag = []
for i in range(n):
    a,b = map(int, input().split())
    bag.append((a,b))

dp = [[float("inf")]*(h+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for i in range(n):
    damage, mana = bag[i]
    for w in range(h+1):
        dp[i+1][w] = min(dp[i+1][w], dp[i][w])
        if w >= damage:
            dp[i+1][w] = min(dp[i+1][w], dp[i+1][w-damage]+mana)

data = dp[-1]
rmq = RangeMinimumQuery(len(data))
rmq.construct(data)
ans = data[-1]
for a,b in bag:
    if a >= h:
        ans = min(ans, b)
    else:
        tmp = rmq.query(h-a, h) + b
        ans = min(ans, tmp)
print(ans)

Solution (Python):
H, N = map(int, input().split())
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]


dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)

print(dp[-1])

Solution (Python):
H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*N]

INF = 10**9
dp = [INF]*(3*(10**4))
dp[0] = 0

for i in range(H+1):
    for a,b in AB:
        dp[i+a] = min(dp[i+a],dp[i]+b)
print(min(dp[H:]))