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

ab=[]

p=0

for i in range(n):

	a,b=list(map(int,input().split()))

	p=max(p,a)

	ab.append([a,b])

dp=[[10**9]*(p+1+h) for _ in range(n+1)]

for i in range(n+1):

	dp[i][0]=0



for i in range(n):

	for j in range(p+h):

		if j+1-ab[i][0]>=0:

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

		else:

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

ans=10**10

for i in range(h,h+p):

	ans=min(dp[n][i],ans)

print(ans)
def main():

	inf=10**9

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

	ab=[]

	r=0

	for i in range(n):

		a,b=list(map(int,input().split()))

		ab.append((a,b))

		r=max(r,a)

	#dp[number][damage]

	dp=[[inf for _ in range(r+h)]for _ in range(n+1)]

	for i in range(n+1):

		dp[i][0]=0

	for i in range(n):

		for j in range(r+h):

			if j-ab[i][0]>=0:

				dp[i+1][j]=dp[i+1][j-ab[i][0]]+ab[i][1]

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

	ans=inf

	for i in range(r):

		ans=min(ans,dp[n][i+h])

	print(ans)

if __name__ == '__main__':

	main()
h, n = list(map(int, input().split()))
ab = []
p = 0
for i in range(n):
    a, b = list(map(int, input().split()))
    p = max(p, a)
    ab.append([a, b])
dp = [[10**9] * (p + 1 + h) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0
for i in range(n):
    for j in range(p + h):
        if j + 1 - ab[i][0] >= 0:
            dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j + 1 - ab[i][0]] + ab[i][1])
        else:
            dp[i + 1][j + 1] = dp[i][j + 1]
ans = 10**10
for i in range(h, h + p):
    ans = min(dp[n][i], ans)
print(ans)

def main():
    inf = 10**9
    h, n = list(map(int, input().split()))
    ab = []
    r = 0
    for i in range(n):
        a, b = list(map(int, input().split()))
        ab.append((a, b))
        r = max(r, a)
    # dp[number][damage]
    dp = [[inf for _ in range(r + h)] for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 0
    for i in range(n):
        for j in range(r + h):
            if j - ab[i][0] >= 0:
                dp[i + 1][j] = dp[i + 1][j - ab[i][0]] + ab[i][1]
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
    ans = inf
    for i in range(r):
        ans = min(ans, dp[n][i + h])
    print(ans)


if __name__ == "__main__":
    main()

-h, n = list(map(int, input().split())) -ab = [] -p = 0 -for i in range(n): -    a, b = list(map(int, input().split())) -    p = max(p, a) -    ab.append([a, b]) -dp = [[10**9] * (p + 1 + h) for _ in range(n + 1)] -for i in range(n + 1): -    dp[i][0] = 0 -for i in range(n): -    for j in range(p + h): -        if j + 1 - ab[i][0] >= 0: -            dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j + 1 - ab[i][0]] + ab[i][1]) -        else: -            dp[i + 1][j + 1] = dp[i][j + 1] -ans = 10**10 -for i in range(h, h + p): -    ans = min(dp[n][i], ans) -print(ans) +def main(): +    inf = 10**9 +    h, n = list(map(int, input().split())) +    ab = [] +    r = 0 +    for i in range(n): +        a, b = list(map(int, input().split())) +        ab.append((a, b)) +        r = max(r, a) +    # dp[number][damage] +    dp = [[inf for _ in range(r + h)] for _ in range(n + 1)] +    for i in range(n + 1): +        dp[i][0] = 0 +    for i in range(n): +        for j in range(r + h): +            if j - ab[i][0] >= 0: +                dp[i + 1][j] = dp[i + 1][j - ab[i][0]] + ab[i][1] +            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j]) +    ans = inf +    for i in range(r): +        ans = min(ans, dp[n][i + h]) +    print(ans) + + +if __name__ == "__main__": +    main()