Problem: Ibis is fighting with a monster.  The _health_ of the monster is H.  Ibis can cast N kinds of spells. Casting the i-th spell decreases the monster's health by A_i, at the cost of B_i Magic Points.  The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.  Ibis wins when the health of the monster becomes 0 or below.  Find the minimum total Magic Points that have to be consumed before winning.

Submission attempts (in order):
# import itertools
# import math
# import sys

# import numpy as np
# from collections import deque
# import heapq

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
H, N = map(int, input().split())
# A = list(map(int, input().split()))
# A = list(map(lambda x: int(x)*(-1), input().split()))
# B = list(map(int, input().split()))
A_B = [list(map(int,input().split())) for _ in range(N)]
# S = input()


# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# edges = [list(map(int,input().split())) for _ in range(N - 1)]
# tree = [[] for _ in range(N + 1)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])



# count = [0] * (N + 1)


#     p, x = map(int, input().split())
#     count[p] += x


#     for l in tree[s]:


#             dfs(tree, l[0])
# dfs(tree, 1)



#     arr = []
#     temp = n

#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr



# bfs
# tree = [[] for _ in range(N + 1)]
# edges = [list(map(int,input().split())) for _ in range(M)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])







# ans = [0] * (N + 1)
# while d:



#      continue

#    ans[i] = v



# print('Yes')
# print(*ans[2:], sep="\n")

max_a = max(a for a, b in A_B)

max_damege = H + max_a

dp = [0] * (max_damege + 1)

for i in range(max_damege + 1):
    dp[i] = min(dp[i-a]+b for a,b in A_B)

print(dp[H-1:])

print(min(dp[H-1:]))

# import itertools
# import math
# import sys

# import numpy as np
# from collections import deque
# import heapq

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
H, N = map(int, input().split())
# A = list(map(int, input().split()))
# A = list(map(lambda x: int(x)*(-1), input().split()))
# B = list(map(int, input().split()))
A_B = [list(map(int,input().split())) for _ in range(N)]
# S = input()


# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# edges = [list(map(int,input().split())) for _ in range(N - 1)]
# tree = [[] for _ in range(N + 1)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])



# count = [0] * (N + 1)


#     p, x = map(int, input().split())
#     count[p] += x


#     for l in tree[s]:


#             dfs(tree, l[0])
# dfs(tree, 1)



#     arr = []
#     temp = n

#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr



# bfs
# tree = [[] for _ in range(N + 1)]
# edges = [list(map(int,input().split())) for _ in range(M)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])







# ans = [0] * (N + 1)
# while d:



#      continue

#    ans[i] = v



# print('Yes')
# print(*ans[2:], sep="\n")

max_a = max(a for a, b in A_B)

max_damege = H + max_a

dp = [0] * (max_damege + 1)

for i in range(max_damege + 1):
    dp[i] = min(dp[i-a]+b for a,b in A_B)

print(min(dp[H-1:]))

Verdicts: Wrong Answer

Accepted