Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

### TESTCASE
test = ""
#test = \
"""
9 3
8 3
4 2
2 1
ans 4
"""

"""
5 2
4 4
2 3
ans 7
"""

"""
100 6
1 1
2 3
3 9
4 27
5 81
6 243
ans 100
"""

"""
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
ans 139815
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
####### MAIN
        
h, n = map(int, input2().split())    
ab = [tuple(map(int, input2().split())) for _ in range(n)]

dp = [0] * (h + 1)

for i in range(1, h+1):
    dp[i] = min(dp[max(i-c[0], 0)] + c[1] for c in ab)
    #print(i, kouho)  
print(dp[-1])
    
    

Fixed submission:
# -*- coding: utf-8 -*-

"""

9 3
8 3
4 2
2 1
ans 4

7 2
4 4
2 3
ans 8

100 6
1 1
2 3
3 9
4 27
5 81
6 243
ans 100

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
ans 139815
"""; test = """
"""
import builtins
test = list(reversed(test.strip().splitlines()))
input = test.pop if test else builtins.input


import numpy as np
h, n = map(int, input().split())    
ab = np.array([tuple(map(int, input().split())) for _ in range(n)])


dp = np.zeros(h + 1, dtype="int")
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i - ab[:, 0], 0)] + ab[:, 1])
    ### dp[i] = min(dp[max(i-c[0], 0)] + c[1] for c in ab) ###
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

### TESTCASE
test = ""
#test = \
"""
9 3
8 3
4 2
2 1
ans 4
"""

"""
5 2
4 4
2 3
ans 7
"""

"""
100 6
1 1
2 3
3 9
4 27
5 81
6 243
ans 100
"""

"""
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
ans 139815
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
####### MAIN
        
h, n = map(int, input2().split())    
ab = [tuple(map(int, input2().split())) for _ in range(n)]

dp = [0] * (h + 1)

for i in range(1, h+1):
    kouho = 10**15
    for c in ab:     
        kouho = min(kouho, dp[max(i-c[0], 0)] + c[1])
    
    dp[i] = kouho
    #print(i, kouho)
        
print(dp[-1])
    
    








Fixed submission:
# -*- coding: utf-8 -*-

"""

9 3
8 3
4 2
2 1
ans 4

7 2
4 4
2 3
ans 8

100 6
1 1
2 3
3 9
4 27
5 81
6 243
ans 100

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
ans 139815
"""; test = """
"""
import builtins
test = list(reversed(test.strip().splitlines()))
input = test.pop if test else builtins.input


import numpy as np
h, n = map(int, input().split())    
ab = np.array([tuple(map(int, input().split())) for _ in range(n)])


dp = np.zeros(h + 1, dtype="int")
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i - ab[:, 0], 0)] + ab[:, 1])
    ### dp[i] = min(dp[max(i-c[0], 0)] + c[1] for c in ab) ###
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

### TESTCASE
test = ""
#test = \
"""
9 3
8 3
4 2
2 1
ans 4
"""

"""
5 2
4 4
2 3
ans 7
"""

"""
100 6
1 1
2 3
3 9
4 27
5 81
6 243
ans 100
"""

"""
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
ans 139815
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
####### MAIN
        
h, n = map(int, input2().split())    
ab = [tuple(map(int, input2().split())) for _ in range(n)]

dp = [0] * (h + 1)

for i in range(1, h+1):
    kouho = [10**15]
    for c in ab:     
        kouho.append(dp[max(i-c[0], 0)] + c[1])
    dp[i] = min(kouho)
    #print(i, kouho)
        
print(dp[-1])
    
    








Fixed submission:
# -*- coding: utf-8 -*-

"""

9 3
8 3
4 2
2 1
ans 4

7 2
4 4
2 3
ans 8

100 6
1 1
2 3
3 9
4 27
5 81
6 243
ans 100

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
ans 139815
"""; test = """
"""
import builtins
test = list(reversed(test.strip().splitlines()))
input = test.pop if test else builtins.input


import numpy as np
h, n = map(int, input().split())    
ab = np.array([tuple(map(int, input().split())) for _ in range(n)])


dp = np.zeros(h + 1, dtype="int")
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i - ab[:, 0], 0)] + ab[:, 1])
    ### dp[i] = min(dp[max(i-c[0], 0)] + c[1] for c in ab) ###
print(dp[-1])