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

ab = [list(map(int,input().split())) for i in range(n)]

#(a,b):=(ダメージ,消費魔力)



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

dp[0] = 0



for i in range(h + 1):

    for j in range(n):

        if dp[i] == float('inf'):continue

        temp_a = i + ab[j][0] if i + ab[j][0] < h else h

        temp_b = dp[i] + ab[j][1]



        dp[temp_a] = min(dp[temp_a], temp_b)



print((dp[-1]))

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

a,b=[],[]

for i in range(n):

    A,B=list(map(int,input().split()))

    a.append(A)#ダメージ量

    b.append(B)#消費魔力



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

dp[0]=0

for i in range(h):

    for j in range(n):



        next=i+a[j] if i+a[j]<=h else h

        dp[next]=min(dp[next],dp[i]+b[j])

print((dp[-1]))

h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(n)]
# (a,b):=(ダメージ,消費魔力)
dp = [float("inf")] * (h + 1)
dp[0] = 0
for i in range(h + 1):
    for j in range(n):
        if dp[i] == float("inf"):
            continue
        temp_a = i + ab[j][0] if i + ab[j][0] < h else h
        temp_b = dp[i] + ab[j][1]
        dp[temp_a] = min(dp[temp_a], temp_b)
print((dp[-1]))
# print(dp)

h, n = list(map(int, input().split()))
a, b = [], []
for i in range(n):
    A, B = list(map(int, input().split()))
    a.append(A)  # ダメージ量
    b.append(B)  # 消費魔力
dp = [float("inf")] * (h + 1)
dp[0] = 0
for i in range(h):
    for j in range(n):
        next = i + a[j] if i + a[j] <= h else h
        dp[next] = min(dp[next], dp[i] + b[j])
print((dp[-1]))

-ab = [list(map(int, input().split())) for i in range(n)] -# (a,b):=(ダメージ,消費魔力) +a, b = [], [] +for i in range(n): +    A, B = list(map(int, input().split())) +    a.append(A)  # ダメージ量 +    b.append(B)  # 消費魔力 -for i in range(h + 1): +for i in range(h): -        if dp[i] == float("inf"): -            continue -        temp_a = i + ab[j][0] if i + ab[j][0] < h else h -        temp_b = dp[i] + ab[j][1] -        dp[temp_a] = min(dp[temp_a], temp_b) +        next = i + a[j] if i + a[j] <= h else h +        dp[next] = min(dp[next], dp[i] + b[j]) -# print(dp)