#動的計画法

import numpy as np

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



A=np.empty(N,dtype=int)

B=np.empty(N,dtype=int)

for i in range(N):

    A[i],B[i]=list(map(int,list(input().split(" "))))



DP=np.empty(H+1,dtype=int)



def battle(hp,magic=0):

  #print(hp,magic)

  if hp==0:

    return magic

  t = hp-A

  t[t<0] = 0

  min_power = min(DP[t]+B)

  return magic+min_power



#DP = [0]*(H+1)

for i in range(H+1):

  DP[i] = battle(i)

  #print(DP[i])

ans = DP[H]

print(ans)



#print(*ans, sep='\n')
def solve():

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

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

    dp = [float('inf')]*(H+10**4)

    dp[0] = 0

    for h in range(1,H+10**4):

        for i in range(N):

            if A[i][0]<=h:

                dp[h] = min(dp[h],dp[h-A[i][0]]+A[i][1])

    ans = min(dp[H:])

    return ans

print((solve()))
# 動的計画法
import numpy as np

H, N = list(map(int, input().split()))
A = np.empty(N, dtype=int)
B = np.empty(N, dtype=int)
for i in range(N):
    A[i], B[i] = list(map(int, list(input().split(" "))))
DP = np.empty(H + 1, dtype=int)


def battle(hp, magic=0):
    # print(hp,magic)
    if hp == 0:
        return magic
    t = hp - A
    t[t < 0] = 0
    min_power = min(DP[t] + B)
    return magic + min_power


# DP = [0]*(H+1)
for i in range(H + 1):
    DP[i] = battle(i)
    # print(DP[i])
ans = DP[H]
print(ans)
# print(*ans, sep='\n')

def solve():
    H, N = list(map(int, input().split()))
    A = [list(map(int, input().split())) for _ in range(N)]
    dp = [float("inf")] * (H + 10**4)
    dp[0] = 0
    for h in range(1, H + 10**4):
        for i in range(N):
            if A[i][0] <= h:
                dp[h] = min(dp[h], dp[h - A[i][0]] + A[i][1])
    ans = min(dp[H:])
    return ans


print((solve()))

-# 動的計画法 -import numpy as np - -H, N = list(map(int, input().split())) -A = np.empty(N, dtype=int) -B = np.empty(N, dtype=int) -for i in range(N): -    A[i], B[i] = list(map(int, list(input().split(" ")))) -DP = np.empty(H + 1, dtype=int) +def solve(): +    H, N = list(map(int, input().split())) +    A = [list(map(int, input().split())) for _ in range(N)] +    dp = [float("inf")] * (H + 10**4) +    dp[0] = 0 +    for h in range(1, H + 10**4): +        for i in range(N): +            if A[i][0] <= h: +                dp[h] = min(dp[h], dp[h - A[i][0]] + A[i][1]) +    ans = min(dp[H:]) +    return ans -def battle(hp, magic=0): -    # print(hp,magic) -    if hp == 0: -        return magic -    t = hp - A -    t[t < 0] = 0 -    min_power = min(DP[t] + B) -    return magic + min_power - - -# DP = [0]*(H+1) -for i in range(H + 1): -    DP[i] = battle(i) -    # print(DP[i]) -ans = DP[H] -print(ans) -# print(*ans, sep='\n') +print((solve()))