CodeEff/ECCO huggingface dataset:
# Original solution
inf = 10 ** 18

h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, _ in ab)
dp = [inf for _ in range(h + max_a)]
dp[0] = 0
for i in range(1, h + max_a):
    min_dp = inf
    for a, b in ab:
        if 0 > i - a:
            continue
        min_dp = min(min_dp, dp[i-a] + b)
    dp[i] = min_dp
print((min(dp[h:])))


# Optimized solution
inf = 10 ** 18
h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, _ in ab)
dp = [inf] * (h + max_a)
dp[0] = 0
for i in range(1, h + max_a):
    dp[i] = min(dp[i-a] + b for a, b in ab)
print((min(dp[h:])))
# Original solution
H, N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

# 個数制限なしナップサック
# i番目までの魔法を使ったときにHダメージを実現できるときの最小の魔力
dp = [[float('inf')]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H+1):
        # i番目の魔法を使わない時
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # i番目の魔法を使う時
        dp[i+1][min(H, j+A[i])] = min(dp[i][j]+B[i], dp[i+1][j]+B[i], dp[i+1][min(j+A[i], H)])

print((dp[N][H]))


# Optimized solution
H, N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

# 個数制限なしナップサック
# i番目までの魔法を使ったときにHダメージを実現できるときの最小の魔力
dp = [[10**10]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H+1):
        # i番目の魔法を使わない時
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # i番目の魔法を使う時
        dp[i+1][min(H, j+A[i])] = min(dp[i][j]+B[i], dp[i+1][j]+B[i], dp[i+1][min(j+A[i], H)])

print((dp[N][H]))
# Original solution
h, n = list(map(int, input().split()))
magics = sorted([list(map(int, input().split())) for _ in range(n)])
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)

dp[0] = 0
for i in range(len(dp)):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print((min(dp[h:])))



# Optimized solution
h, n = list(map(int, input().split()))
magics = sorted(list(map(int, input().split())) for _ in range(n))
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(h+max_cost):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print((min(dp[h:])))
# Original solution
h, n = list(map(int, input().split()))
magics = sorted(list(map(int, input().split())) for _ in range(n))
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(h+max_cost):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print((min(dp[h:])))



# Optimized solution
import sys

input = sys.stdin.readline

h, n = list(map(int, input().split()))

magics = []
max_cost = 0
for _ in range(n):
    at, cost = list(map(int, input().split()))
    max_cost = max(max_cost, cost)
    magics.append((at, cost))

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(len(dp)):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
print((min(dp[h:])))
# Original solution
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)
memo = [None]*(H+1)
memo[0] = 0
for h in range(1,H+1):
    memo[h] = memo[max(0,h-dec[0])]+cost[0]
    for i in range(1,N):
        memo[h] = min(memo[h], memo[max(0,h-dec[i])]+cost[i])
print((memo[H]))

# Optimized solution
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]))
# Original solution
H,N = list(map(int,input().split()))
dp = [float("inf")] * (H+1)

for i in range(N):
  a,b = list(map(int,input().split()))

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

print((dp[-1]))


# Optimized solution
H,N = list(map(int,input().split()))
INF = float('inf')
# dp[i] = 攻撃がh以上となるときに考えられる最小の体力消耗
dp = [INF] * (H+1)

for _ in range(N):
  a,b = list(map(int,input().split()))

  for h in range(1, H+1):
    if h <= a:
      dp[h] = min(dp[h],b)
    else:
      dp[h] = min(dp[h],dp[h-a]+b)

print((dp[-1]))
# Original solution
#coding:utf-8

def main():
    h, n = list(map(int, input().split()))
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    
    inf = 100000000000
    # indexがモンスターに与えたダメージで、中身がトキのダメージ
    damages = [0] + [inf] * h
    for i in range(1, h + 1):
        for j in range(n):
            damage_monster = ab[j][0]
            damage_toki = ab[j][1]
            
            damages[i] = min(damages[max(0, i - damage_monster)] + damage_toki, damages[i])


    print((min(damages[h:])))
main()

# Optimized solution
#coding:utf-8
 
def main():
    h, n = list(map(int, input().split()))
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    
    inf = 100000000000
    # indexがモンスターに与えたダメージで、中身がトキのダメージ
    damages = [inf for _ in range(100000)]
    damages[0] = 0
    pre_damage = -1
    for i in range(h):
        if damages[i] == inf:
            continue
        for j in range(n):
            new_damage = ab[j][0]
            if damages[i + new_damage] > damages[i] + ab[j][1]:
                damages[i + new_damage] = damages[i] + ab[j][1]
        
 
    print((min(damages[h:])))
main()
# Original solution
def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    H, N = list(map(int, input().split()))
    M = [tuple(map(int, readline().split())) for _ in range(N)]
    INF = 10 ** 9
    dp = [INF] * (H + 1)
    dp[0] = 0
    
    for i in range(N):
        a, b = M[i]
        for j in range(H):
            nj = min(H, j + a)
            dp[nj] = min(dp[nj], dp[j] + b)

    print((dp[H]))


if __name__ == "__main__":
    main()


# Optimized solution
def main():
    import sys
    # readline = sys.stdin.readline
    readlines = sys.stdin.readlines
    H, N = list(map(int, input().split()))
    M = [tuple(map(int, s.split())) for s in readlines()]
    INF = 10 ** 9
    dp = [INF] * (H + 1)
    dp[0] = 0
    
    for i in range(N):
        a, b = M[i]
        for j in range(H):
            nj = min(H, j + a)
            dp[nj] = min(dp[nj], dp[j] + b)

    print((dp[H]))


if __name__ == "__main__":
    main()
# Original solution
import sys

H, N = list(map(int, input().split()))
A = [0] * N
B = [0] * N

for i in range(N):
    a, b = list(map(int, sys.stdin.readline().rstrip().split()))
    A[i] = a
    B[i] = b

max_A = max(A)
INF = 10**18
dp = [INF] * (H + max_A)
dp[0] = 0

for i in range(0, H):
    for j in range(N):
        dp[i + A[j]] = min(dp[i] + B[j], dp[i + A[j]])

print((min(dp[H:H + max_A])))


# Optimized solution
import sys

H, N = list(map(int, input().split()))
A = [0] * N
B = [0] * N

for i in range(N):
    a, b = list(map(int, sys.stdin.readline().rstrip().split()))
    A[i] = a
    B[i] = b

max_A = max(A)
INF = 10**18
dp = [INF] * (H + max_A)
dp[0] = 0

for i in range(H):
    for j in range(N):
        dp[i + A[j]] = min(dp[i] + B[j], dp[i + A[j]])

print((min(dp[H:H + max_A])))
# Original solution
H, N = list(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]))

# Optimized solution
import sys
input=sys.stdin.readline

def main():
    H, N = list(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()
# Original solution
H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for i in range(N)]

INF = 10**10+1

dp = [[INF]*(H+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    dp[i][0] = 0
    A = AB[i-1][0]
    for j in range(1, H+1):
        if j-AB[i-1][0]>=0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-AB[i-1][0]]+AB[i-1][1], dp[i][j-AB[i-1][0]]+AB[i-1][1])
        else:
            dp[i][j] = min(dp[i-1][j], AB[i-1][1])

print((dp[N][H]))

# Optimized solution
H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for i in range(N)]

INF = 10**10+1

dp = [[INF]*(H+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    dp[i][0] = 0
    A = AB[i-1][0]
    for j in range(1, H+1):
        if j-AB[i-1][0]>=0:
            dp[i][j] = min(dp[i-1][j], dp[i][j-AB[i-1][0]]+AB[i-1][1])
        else:
            dp[i][j] = min(dp[i-1][j], AB[i-1][1])

print((dp[N][H]))
# Original solution
H,N = list(map(int,input().split()))
magic = [list(map(int,input().split())) for i in range(N)]

INF = 10**10
#print(magic)

AM = 0
for i in range(N):
    AM = max(AM,magic[i][0])
#print(AM)


dp = [INF for i in range(H+AM+1)]
dp[0] = 0

for i in range(1,H+AM+1):
    for j in range(N):
        if magic[j][0] > i:
            dp[i] = min(dp[i],magic[j][1])
        else:
            dp[i] = min(dp[i-magic[j][0]]+magic[j][1],dp[i])
ans = INF
for i in range(H,H+AM+1):
    ans = min(ans,dp[i])
print(ans)



# Optimized solution
H,N = list(map(int,input().split()))
magic = [list(map(int,input().split())) for i in range(N)]

INF = 10**10
#print(magic)

AM = 0
for i in range(N):
    AM = max(AM,magic[i][0])
#print(AM)


dp = [INF for i in range(H+AM+1)]
dp[0] = 0

for i in range(1,H+AM+1):
    for j in range(N):
        if magic[j][0] > i:
            dp[i] = min(dp[i],magic[j][1])
        else:
            dp[i] = min(dp[i-magic[j][0]]+magic[j][1],dp[i])
ans = INF
print((dp[H]))
# Original solution
h,n= list(map(int, input().split()))
p = [list(map(int, input().split())) for _ in range(n)]
dp = [0]*(h+10**4)
for i in range(1,h+10**4):
  dp[i] = min(dp[i-a] + b for a,b in p)
print((min(dp[h:])))

# Optimized solution
h,n= list(map(int, input().split()))
p = [list(map(int, input().split())) for _ in range(n)] 
m = 10**4
dp = [0]*(h+m+1)
for i in range(m+1,h+m+1):
  dp[i] = min(dp[i-a] + b for a,b in p)
print((dp[h+m]))
# Original solution
def resolve():
    h, n = list(map(int, input().split()))
    w = []
    v = []
    for i in range(n):
        a, b = list(map(int, input().split()))
        w.append(a)
        v.append(b)
    dp = [[0 for i in range(h + 1)] for j in range(n + 1)]
    for i in range(1, h + 1):
        # dp[0][i] = v[0] * ((w[0]+i-1)//w[0])
        dp[0][i] = float("inf")
    for i in range(n):
        # print(dp[i])
        # print(dp[i][::-1][::w[i]]+[0])
        for j in range(h + 1):
            if j >= w[i]:
                dp[i + 1][j] = min([x + y * v[i]
                                    for y, x in enumerate(dp[i][:j+1][::-1][::w[i]]+[0])])
            else:
                dp[i + 1][j] = min(dp[i][j], v[i])
    # print(dp[n])
    print((dp[n][h]))


if __name__ == '__main__':
    resolve()


# Optimized solution
def resolve():
    h, n = list(map(int, input().split()))
    w = []
    v = []
    for i in range(n):
        a, b = list(map(int, input().split()))
        w.append(a)
        v.append(b)
    dp = [[0 for i in range(h + 1)] for j in range(n + 1)]
    for i in range(1, h + 1):
        dp[0][i] = float("inf")
    for i in range(n):
        for j in range(h + 1):
            if j >= w[i]:
                dp[i + 1][j] = min(dp[i + 1][j - w[i]] + v[i], dp[i][j])
            else:
                dp[i + 1][j] = min(dp[i][j], v[i])
    # print(dp[n])
    print((dp[n][h]))


if __name__ == '__main__':
    resolve()
# Original solution
def main():
    h, n = list(map(int, input().split()))
    magic_list = []

    for _ in range(n):
        a, b = list(map(int, input().split()))
        magic_list.append((a, b))

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    # 1-origin
    inf = 1 << 40
    max_attack = max(magic_list)[0]
    dp = [inf] * (h + max_attack)
    dp[0] = 0

    # time O(HN)
    for hp in range(1, h + max_attack):
        for attack, mp in magic_list:
            if hp >= attack:
                dp[hp] = min(dp[hp], dp[hp - attack] + mp)

    return min(dp[h:])


main()


# Optimized solution
def main():
    h, n = list(map(int, input().split()))
    magic_list = []

    for _ in range(n):
        a, b = list(map(int, input().split()))
        magic_list.append((a, b))

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    # 1-origin
    max_attack = max(magic_list)[0]
    dp = [0] * (h + max_attack)

    # time O(HN)
    for hp in range(1, h + 1):
        dp[hp] = min(dp[hp - attack] + mp for attack, mp in magic_list)

    return dp[h]


main()
# Original solution
h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]

dp = [0] * (h+max(a for a,b in ab))
for i in range(1, len(dp)):
    dp[i] = min([float('inf')] + [(dp[i-a]+b) for a, b in ab if i-a >= 0])
print((min(dp[h:])))


# Optimized solution
h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]

dp = [0] * (h+max(a for a,b in ab))
for i in range(1, len(dp)):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print((min(dp[h:])))
# Original solution
h, n = list(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])))


# Optimized solution
h, n = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(n)]
INF = 10**18

dp = [INF] * (h + 1)
dp[h] = 0
for i in range(n):
    a, b = info[i]
    for j in range(h + 1)[::-1]:
            dp[max(j - a, 0)] = min(dp[j] + b, dp[max(j - a, 0)])
print((dp[0]))
# Original solution
h, n = list(map(int, input().split()))

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

dp = [[float('inf') for _ in range(h+1)] for _ in range(n+1)]
dp[0][0] = 0
#print(attack, magic)
for i in range(n):
    for j in range(h+1):
        #print(max(dp[i][j], dp[i][j-attack[i]] + magic[i]))
        if dp[i+1][j] > dp[i][j]: dp[i+1][j] = dp[i][j]
        if dp[i+1][min(j+attack[i], h)] > dp[i+1][j]+magic[i]: dp[i+1][min(j+attack[i], h)] = dp[i+1][j]+magic[i]

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

# Optimized solution
h, n = list(map(int, input().split()))
magic = [tuple(map(int, input().split())) for _ in range(n)]
#magic = [list(map(int, input().split())) for _ in range(n)]

dp = [float('inf')] * (h+1)
dp[0] = 0

for i in range(h):
    for d, c in magic:
        next_index = min(i+d, h)
        dp[next_index] = min(dp[next_index], dp[i]+c)
        #print(d, c, dp)

print((dp[-1]))
# Original solution
import sys

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

dp = [0] * (H + 1)

for i in range(1, H + 1):
    dp[i] = min(dp[max(i - damage, 0)] + cost for damage, cost in magic)

ans = dp[H]

print(ans)


# Optimized solution
import sys

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

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for i in range(1, H + max_damage):
    dp[i] = min(dp[i - damage] + cost for damage, cost in magic)

ans = min(dp[H:])

print(ans)
# Original solution
from sys import stdin
f_i = stdin

H, N = list(map(int, f_i.readline().split()))

dp = [10 ** 8] * (H + 10 ** 4)
dp[0] = 0

for i in range(N):
    A, B = list(map(int, f_i.readline().split()))
    for j, t in enumerate(zip(dp, dp[A:H+A]), start=A):
        dp_i, dp_j = t
        if dp_i + B < dp_j:
            dp[j] = dp_i + B

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

# Optimized solution
def solve():
    from sys import stdin
    f_i = stdin
    
    H, N = list(map(int, f_i.readline().split()))
    
    dp = [10 ** 8] * (H + 10 ** 4)
    dp[0] = 0
    
    for i in range(N):
        A, B = list(map(int, f_i.readline().split()))
        for j, t in enumerate(zip(dp, dp[A:H+A]), start=A):
            dp_i, dp_j = t
            if dp_i + B < dp_j:
                dp[j] = dp_i + B
    
    print((min(dp[H:])))

solve()
# Original solution
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    H, N = list(map(int, input().rstrip().split()))
    magic_list = []
    for _ in range(N):
        A, B = list(map(int, input().rstrip().split()))
        magic_list.append((A, B))

    dp = [[100000000] * (H+1) for _ in range(N+1)]
    # dp[i][hp] = i番目までの魔法を使って、hpのダメージを与えるための最小魔力
    dp[0][0] = 0
    for i, magic in enumerate(magic_list):
        damage, mp = magic
        for hp in range(H+1):
            # i番目までの魔法を使って、与えられるダメージの最小魔力の結果をコピー
            dp[i+1][hp] = min(dp[i+1][hp], dp[i][hp])
            # 魔法を使用する場合、i+1番目までの魔法を使って、HP+damageのダメージの魔力最小値であれば更新
            dp[i+1][min(H, hp+damage)] = min(dp[i+1][min(H, hp+damage)], dp[i+1][hp] + mp)
    print((dp[N][H]))

if __name__ == '__main__':
    main()

# Optimized solution
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    H, N = list(map(int, input().rstrip().split()))
    magic_list = []
    for _ in range(N):
        A, B = list(map(int, input().rstrip().split()))
        magic_list.append((A, B))

    # dp[hp] = hpのダメージを与えるための最小魔力
    dp = [100000000] * (H+1)
    # 0のダメージを与えるのに必要な最小魔力は0
    dp[0] = 0
    # 各魔法に関して探索
    for i, magic in enumerate(magic_list):
        damage, mp = magic
        # 各ダメージを与えるのに必要な最小魔力を更新する
        # (与えられないダメージ数の場合は最大値で初期化してあるので、最大値のまま更新されない)
        for hp in range(H+1):
            # 魔法を使用する場合のダメージについて、必要魔力が現在計算されている中での最小値であれば更新
            dp[min(H, hp+damage)] = min(dp[min(H, hp+damage)], dp[hp] + mp)
    print((dp[H]))

if __name__ == '__main__':
    main()
# Original solution
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    h,n=list(map(int, input().split()))
    ab=[list(map(int, input().split())) for i in range(n)]
    ans=[0]*(h+1)
    for i in range(1,h+1):
        li = [ans[max(i-j[0],0)]+j[1] for j in ab]
        ans[i]=min(li)
    print((ans[h]))

if __name__=='__main__':
    main()

# Optimized solution
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    h,n=list(map(int, input().split()))
    ab=[list(map(int, input().split())) for i in range(n)]
    ans=[0]*(4*10**4)
    for i in range(1,h+1):
        li = [ans[i-j[0]]+j[1] for j in ab]
        ans[i]=min(li)
    print((ans[h]))

if __name__=='__main__':
    main()
# Original solution
H, N = list(map(int, input().split()))

A, B = [0] * N, [0] * N
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))

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

dp[0][0] = 0

for i in range(N):
    for j in range(H+1):
        nj = min(j+A[i], H)

        dp[i+1][nj] = min(dp[i][nj], dp[i+1][j] + B[i])

print((dp[N][H]))

# Optimized solution
H, N = list(map(int, input().split()))

A, B = [0] * N, [0] * N

for i in range(N):
    A[i], B[i] = list(map(int, input().split()))

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

for i in range(N):
    for j in range(H+1):
        nj = min(j+A[i], H)
        dp[nj] = min(dp[nj], dp[j]+B[i])
print((dp[H]))
# Original solution
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

H, N = list(map(int, input().split()))
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()


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


print((dp(H)))


# Optimized solution
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

H, N = list(map(int, input().split()))
AB = [tuple(map(int, input().split())) for _ in range(N)]
# 効率順にソート
# 効率が同じなら、小規模な魔法を優先
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))


@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float("inf")
        for a, b in AB:
            val = b + dp(h - a)
            if val < best:
                best = val
            else:
                # 更新されなかった場合は、以降の魔法で更新されることはない
                break
        return best


print((dp(H)))
# Original solution
# -*- coding: utf-8 -*-

# 入力を整数に変換して受け取る
def input_int():
    return int(eval(input()))


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return list(map(int, input().split()))


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    h, n = input_to_int_map()
    ab = [input_to_int_tuple() for i in range(n)]

    x = max(a for a, b in ab)

    dp = [0] * (h + x)
    for i in range(1, h + 1):

        min_val = 9999999999
        for a, b in ab:
                min_val = min(min_val, dp[i - a] + b)

        dp[i] = min_val

    return dp[h]


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


# Optimized solution
# -*- coding: utf-8 -*-

# 入力を整数に変換して受け取る
def input_int():
    return int(eval(input()))


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return list(map(int, input().split()))


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    h, n = input_to_int_map()
    ab = [input_to_int_tuple() for i in range(n)]

    x = max(a for a, b in ab)

    dp = [0] * (h + x)
    for i in range(1, h + 1):

        dp[i] = min(dp[i - a] + b for a, b in ab)

    return dp[h]


if __name__ == "__main__":
    print((main()))
# Original solution
H,N=list(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]))

# Optimized solution
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(H, N, AB):
    INF = 10**9
    dp = [INF] * (H + 1)
    dp[H] = 0
    for h in reversed(list(range(H + 1))):
        for i, (a, b) in enumerate(AB):
            nh = max(0, h - a)
            dp[nh] = min(dp[nh], dp[h] + b)
    print((dp[0]))

if __name__ == '__main__':
    input = sys.stdin.readline
    H, N = list(map(int, input().split()))
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    main(H, N, AB)
# Original solution
import sys
input = sys.stdin.readline
def main():
    h, n = (int(x) for x in input().split())
    ab = []
    for _ in range(n):
        a, b = (int(x) for x in input().split())
        ab.append([a, b])
    dp = [float('inf')] * (h)
    for a, b in ab:
        for i in range(h):
            if i < a:
                dp[i] = min(dp[i], b)
            else:
                dp[i] = min(dp[i], dp[i - a] + b)
    print((dp[h - 1]))
if __name__=='__main__':
    main()

# Optimized solution
h, n = (int(x) for x in input().split())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
max_a = max(a for a, _ in ab)
dp = [0] * (h + max_a)
for i in range(1, h + 1):
    dp[i] = min(dp[i - a] + b for a, b in ab)
print((dp[h]))