Buggy python submission (verdict: Time Limit Exceeded):
'''
# 以下はTLである
H, N = map(int, input().split())
magic = []
# Aは威力Bは消費魔力
for i in range(N):
    A, B = map(int, input().split())
    magic.append([A,B])

# DPで解く
# DP[i]ダメージをi与えた時の最低使用魔力
# DP[H]ダメージがH以上になったときの最低使用魔力
# DP[i] = -1 のときは計算しない
DP = [-1 for _ in range(H+1)]
DP[0] = 0

for i in range(H):
    if DP[i] == -1:
        pass
    else:
        for j in range(N):
            h = i + magic[j][0]
            mp = DP[i] + magic[j][1]
            if h <= H and DP[h] == -1:
                DP[h] = mp
            elif h <= H and DP[h] != -1:
                if DP[h] > mp:
                    DP[h] = mp
            elif h > H and DP[H] == -1:
                DP[H] = mp
            elif h >H and DP[H] != -1:
                if DP[H] > mp:
                    DP[H] = mp

#print(DP)
print(DP[H])
'''



def test_func(dp, A_list, B_list, i, N):
    # 参考return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))
    magic = []
    for j in range(N):
        # 考えたいiに対してその元となるdpが存在するか
        if i >= A_list[j]:
            magic.append(dp[i-A_list[j]] + B_list[j])
        # 初めての
        else:
            magic.append(B_list[j])
    # 一番魔力がかからなかったものを採用する
    return min(magic)

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

dp = [0 for _ in range(H+1)]

for i in range(1,H+1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

print(dp[H])

Fixed submission:
'''
# 以下はTLである
H, N = map(int, input().split())
magic = []
# Aは威力Bは消費魔力
for i in range(N):
    A, B = map(int, input().split())
    magic.append([A,B])

# DPで解く
# DP[i]ダメージをi与えた時の最低使用魔力
# DP[H]ダメージがH以上になったときの最低使用魔力
# DP[i] = -1 のときは計算しない
DP = [-1 for _ in range(H+1)]
DP[0] = 0

for i in range(H):
    if DP[i] == -1:
        pass
    else:
        for j in range(N):
            h = i + magic[j][0]
            mp = DP[i] + magic[j][1]
            if h <= H and DP[h] == -1:
                DP[h] = mp
            elif h <= H and DP[h] != -1:
                if DP[h] > mp:
                    DP[h] = mp
            elif h > H and DP[H] == -1:
                DP[H] = mp
            elif h >H and DP[H] != -1:
                if DP[H] > mp:
                    DP[H] = mp

#print(DP)
print(DP[H])
'''


'''
# 改善しているがこれもTL
# おそらく関数のappendが足を引っ張っている
def test_func(dp, A_list, B_list, i, N):
    # 参考return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))
    magic = []
    for j in range(N):
        # 考えたいiに対してその元となるdpが存在するか
        if i >= A_list[j]:
            magic.append(dp[i-A_list[j]] + B_list[j])
        # 初めての
        else:
            magic.append(B_list[j])
    # 一番魔力がかからなかったものを採用する
    return min(magic)

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

dp = [0 for _ in range(H+1)]

for i in range(1,H+1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

print(dp[H])
'''

def test_func(dp, A_list, B_list, i, N):
    return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))
    '''
    # 最初から配列に格納
    magic = []
    for j in range(N):
        # 考えたいiに対してその元となるdpが存在するか
        if i >= A_list[j]:
            magic.append(dp[i-A_list[j]] + B_list[j])
        # 初めての
        else:
            magic.append(B_list[j])
    # 一番魔力がかからなかったものを採用する
    return min(magic)
    '''
H, N = map(int, input().split())
A_list = []
B_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)

dp = [0 for _ in range(H+1)]

for i in range(1,H+1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
magic = []
# Aは威力Bは消費魔力
for i in range(N):
    A, B = map(int, input().split())
    magic.append([A,B])

# DPで解く
# DP[i]ダメージをi与えた時の最低使用魔力
# DP[H]ダメージがH以上になったときの最低使用魔力
# DP[i] = -1 のときは計算しない
DP = [-1 for _ in range(H+1)]
DP[0] = 0

for i in range(H):
    if DP[i] == -1:
        pass
    else:
        for j in range(N):
            h = i + magic[j][0]
            mp = DP[i] + magic[j][1]
            if h <= H and DP[h] == -1:
                DP[h] = mp
            elif h <= H and DP[h] != -1:
                if DP[h] > mp:
                    DP[h] = mp
            elif h > H and DP[H] == -1:
                DP[H] = mp
            elif h >H and DP[H] != -1:
                if DP[H] > mp:
                    DP[H] = mp

#print(DP)
print(DP[H])

Fixed submission:
'''
# 以下はTLである
H, N = map(int, input().split())
magic = []
# Aは威力Bは消費魔力
for i in range(N):
    A, B = map(int, input().split())
    magic.append([A,B])

# DPで解く
# DP[i]ダメージをi与えた時の最低使用魔力
# DP[H]ダメージがH以上になったときの最低使用魔力
# DP[i] = -1 のときは計算しない
DP = [-1 for _ in range(H+1)]
DP[0] = 0

for i in range(H):
    if DP[i] == -1:
        pass
    else:
        for j in range(N):
            h = i + magic[j][0]
            mp = DP[i] + magic[j][1]
            if h <= H and DP[h] == -1:
                DP[h] = mp
            elif h <= H and DP[h] != -1:
                if DP[h] > mp:
                    DP[h] = mp
            elif h > H and DP[H] == -1:
                DP[H] = mp
            elif h >H and DP[H] != -1:
                if DP[H] > mp:
                    DP[H] = mp

#print(DP)
print(DP[H])
'''


'''
# 改善しているがこれもTL
# おそらく関数のappendが足を引っ張っている
def test_func(dp, A_list, B_list, i, N):
    # 参考return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))
    magic = []
    for j in range(N):
        # 考えたいiに対してその元となるdpが存在するか
        if i >= A_list[j]:
            magic.append(dp[i-A_list[j]] + B_list[j])
        # 初めての
        else:
            magic.append(B_list[j])
    # 一番魔力がかからなかったものを採用する
    return min(magic)

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

dp = [0 for _ in range(H+1)]

for i in range(1,H+1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

print(dp[H])
'''

def test_func(dp, A_list, B_list, i, N):
    return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))
    '''
    # 最初から配列に格納
    magic = []
    for j in range(N):
        # 考えたいiに対してその元となるdpが存在するか
        if i >= A_list[j]:
            magic.append(dp[i-A_list[j]] + B_list[j])
        # 初めての
        else:
            magic.append(B_list[j])
    # 一番魔力がかからなかったものを採用する
    return min(magic)
    '''
H, N = map(int, input().split())
A_list = []
B_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)

dp = [0 for _ in range(H+1)]

for i in range(1,H+1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

print(dp[H])