import numpy as np

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

ATK, MP = np.array(tuple(tuple(map(int, input().split())) for _ in range(N)), dtype=np.int64).T

MAX_ATK = ATK.max()

table = np.zeros((H + MAX_ATK,), dtype=np.int64)

for damage in range(1, H + 1):

    table[damage] = (table[damage - ATK[np.arange(N, dtype=np.int16)]] + MP[np.arange(N, dtype=np.int16)]).min()

print((table[H]))

import numpy as np

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

ATK, MP = np.array(tuple(tuple(map(int, input().split())) for _ in range(N)), dtype=np.int64).T

MAX_ATK = ATK.max()

table = np.zeros((H + MAX_ATK,), dtype=np.int64)

for damage in range(1, H + 1):

    table[damage] = (table[damage - ATK] + MP).min()

print((table[H]))

import numpy as np

H, N = list(map(int, input().split()))
ATK, MP = np.array(
    tuple(tuple(map(int, input().split())) for _ in range(N)), dtype=np.int64
).T
MAX_ATK = ATK.max()
table = np.zeros((H + MAX_ATK,), dtype=np.int64)
for damage in range(1, H + 1):
    table[damage] = (
        table[damage - ATK[np.arange(N, dtype=np.int16)]]
        + MP[np.arange(N, dtype=np.int16)]
    ).min()
print((table[H]))

import numpy as np

H, N = list(map(int, input().split()))
ATK, MP = np.array(
    tuple(tuple(map(int, input().split())) for _ in range(N)), dtype=np.int64
).T
MAX_ATK = ATK.max()
table = np.zeros((H + MAX_ATK,), dtype=np.int64)
for damage in range(1, H + 1):
    table[damage] = (table[damage - ATK] + MP).min()
print((table[H]))

-    table[damage] = ( -        table[damage - ATK[np.arange(N, dtype=np.int16)]] -        + MP[np.arange(N, dtype=np.int16)] -    ).min() +    table[damage] = (table[damage - ATK] + MP).min()