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

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



#dp[v]:体力をv減らす時の最小魔力

dp=[10**20 for i in range(h+1)]

dp[0]=0



for i in range(h+1):

    for j in range(n):

        if i-x[j][0]<0:

            dp[i] = min(dp[i], dp[0] + x[j][1])



        else:

            dp[i]=min(dp[i],dp[i-x[j][0]]+x[j][1])

print((dp[-1]))

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

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



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

dp[0]=0

for i in range(n):

    x=a[i][0]

    y=a[i][1]

    for j in range(h+1):

        if j>=x:

            dp[j]=min(dp[j-x]+y,dp[j])

        else:

            dp[j]=min(y,dp[j])



print((dp[-1]))
h, n = list(map(int, input().split()))
x = [list(map(int, input().split())) for i in range(n)]
# dp[v]:体力をv減らす時の最小魔力
dp = [10**20 for i in range(h + 1)]
dp[0] = 0
for i in range(h + 1):
    for j in range(n):
        if i - x[j][0] < 0:
            dp[i] = min(dp[i], dp[0] + x[j][1])
        else:
            dp[i] = min(dp[i], dp[i - x[j][0]] + x[j][1])
print((dp[-1]))

h, n = list(map(int, input().split()))
a = [list(map(int, input().split())) for i in range(n)]
dp = [float("inf")] * (h + 1)
dp[0] = 0
for i in range(n):
    x = a[i][0]
    y = a[i][1]
    for j in range(h + 1):
        if j >= x:
            dp[j] = min(dp[j - x] + y, dp[j])
        else:
            dp[j] = min(y, dp[j])
print((dp[-1]))

-x = [list(map(int, input().split())) for i in range(n)] -# dp[v]:体力をv減らす時の最小魔力 -dp = [10**20 for i in range(h + 1)] +a = [list(map(int, input().split())) for i in range(n)] +dp = [float("inf")] * (h + 1) -for i in range(h + 1): -    for j in range(n): -        if i - x[j][0] < 0: -            dp[i] = min(dp[i], dp[0] + x[j][1]) +for i in range(n): +    x = a[i][0] +    y = a[i][1] +    for j in range(h + 1): +        if j >= x: +            dp[j] = min(dp[j - x] + y, dp[j]) -            dp[i] = min(dp[i], dp[i - x[j][0]] + x[j][1]) +            dp[j] = min(y, dp[j])