import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)

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

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


@lru_cache(maxsize=None)
def f(h):
    if h <= 0:
        return 0
    best = float("inf")
    for a, b in AB:
        val = b + f(h - a)
        if val < best:
            best = val
        else:
            # TLE if you don't have the break
            # But I can't prove that it's safe to break
            break
    return best

# Sort by the most efficient spells
AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)

print(f(H))