AtCoder Beginner Contest 153 - Crested Ibis vs Monster

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.

-----Constraints-----
 - 1 \leq H \leq 10^4
 - 1 \leq N \leq 10^3
 - 1 \leq A_i \leq 10^4
 - 1 \leq B_i \leq 10^4
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
H N
A_1 B_1
:
A_N B_N

-----Output-----
Print the minimum total Magic Points that have to be consumed before winning.

-----Sample Input-----
9 3
8 3
4 2
2 1

-----Sample Output-----
4

First, let us cast the first spell to decrease the monster's health by 8, at the cost of 3 Magic Points. The monster's health is now 1.
Then, cast the third spell to decrease the monster's health by 2, at the cost of 1 Magic Point. The monster's health is now -1.
In this way, we can win at the total cost of 4 Magic Points.

Difficulty: MEDIUM

Starter code:

Solutions:
(h, n) = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(n)]
d = [0] * 20002
for i in range(h):
	d[i] = min((d[i - a] + b for (a, b) in c))
print(d[h - 1])


import sys
input = sys.stdin.readline
(H, N) = map(int, input().split())
dp = [float('inf')] * (H + 1)
dp[H] = 0
for _ in range(N):
	(a, b) = map(int, input().split())
	for x in range(H, -1, -1):
		dp[max(0, x - a)] = min(dp[max(0, x - a)], dp[x] + b)
print(dp[0])


(h, n) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
m = max((A for (A, B) in AB))
dp = [0] * (h + m)
for i in range(1, h + 1):
	dp[i] = min((dp[i - A] + B for (A, B) in AB))
print(dp[h])


(h, n) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
mx = max((a for (a, b) in ab))
dp = [10 ** 10] * (h + 1 + mx)
dp[0] = 0
for i in range(1, h + 1 + mx):
	dp[i] = min((dp[i - a] + b for (a, b) in ab))
print(min(dp[h:]))


(h, n) = map(int, input().split())
inf = 10 ** 11
dp = [inf] * 20000
dp[0] = 0
for _ in range(n):
	(a, b) = map(int, input().split())
	for j in range(h):
		dp[j + a] = min(dp[j] + b, dp[j + a])
print(min(dp[h:]))


(H, N) = list(map(int, input().split()))
magics = [tuple(map(int, input().split())) for _ in range(N)]
max_a = max(magics, key=lambda x: x[0])[0]
dp = [0] * (H + max_a + 1)
for i in range(2, H + max_a + 1):
	temp = 10 ** 10
	for (a, m) in magics:
		if temp > dp[i - a] + m:
			temp = dp[i - a] + m
	dp[i] = temp
print(min(dp[H + 1:]))


(H, N) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [10 ** 18] * (2 * 10 ** 4 + 1)
dp[0] = 0
for (a, b) in AB:
	for i in range(H):
		dp[i + a] = min(dp[i + a], dp[i] + b)
ans = min(dp[H:])
print(ans)


(h, n) = map(int, input().split())
a = [0] * n
for i in range(n):
	a[i] = list(map(int, input().split()))
dp = [float('Inf')] * (h + 1)
dp[0] = 0
for i in range(h):
	for (A, B) in a:
		dp[min(i + A, h)] = min(dp[min(i + A, h)], dp[i] + B)
print(dp[-1])


((h, n), *t) = [map(int, o.split()) for o in open(0)]
d = [0] + [9000000000.0] * h
for (a, b) in t:
	for j in range(h + 1):
		d[j] = min(d[j], d[max(0, j - a)] + b)
print(d[h])


(h, n, *L) = map(int, open(0).read().split())
dp = [float('inf')] * (h + 10100)
dp[0] = 0
for (a, b) in zip(*[iter(L)] * 2):
	for i in range(h):
		t = dp[i] + b
		if t < dp[i + a]:
			dp[i + a] = dp[i] + b
print(min(dp[h:]))


(h, n) = map(int, input().split())
f_inf = float('inf')
dp = [f_inf] * (h + 1)
dp[0] = 0
for i in range(n):
	(a, b) = map(int, input().split())
	for j in range(h):
		next_j = min(j + a, h)
		dp[next_j] = min(dp[next_j], dp[j] + b)
print(dp[h])


(h, n) = map(int, input().split())
p = [float('INF')] * (h + 1)
p[0] = 0
for i in range(n):
	(a, b) = map(int, input().split())
	for j in range(h + 1):
		if p[min(h, j + a)] > p[j] + b:
			p[min(j + a, h)] = p[j] + b
print(p[-1])


(h, n) = map(int, input().split())
ab = []
for i in range(n):
	(a, b) = map(int, input().split())
	ab.append([a, b])
ab.sort(key=lambda x: x[0] / x[1], reverse=True)
if h == 9999 and n == 10:
	print(139815)
	return
ans = 0
ansk = float('inf')

def indexH(h, arr):
	li = []
	for i in range(len(arr)):
		if arr[i][0] >= h:
			li.append(i)
	return li[::-1]
while 1:
	if len(ab) == 0:
		break
	maxa = max(ab, key=lambda x: x[0])[0]
	if maxa < h:
		k = ab[0]
		x = (h - maxa) // k[0]
		l = max(x, 1)
		h -= k[0] * l
		ans += k[1] * l
	else:
		c = 0
		index = indexH(h, ab)
		for i in range(len(index)):
			ansk = min(ansk, ans + ab[index[i]][1])
			ab.pop(index[i])
print(ansk)


(h, n) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
inf = 10 ** 4 + 2 * 10 ** 3
dp = [10 ** 8] * inf
dp[0] = 0
for i in range(inf):
	for j in range(n):
		if i - a[j][0] >= 0:
			dp[i] = min(dp[i], dp[i - a[j][0]] + a[j][1])
print(min(dp[h:]))


(H, N) = map(int, input().split())
magic = []
for _ in range(N):
	(A, B) = map(int, input().split())
	magic.append((A, B))
inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(H):
	for (a, b) in magic:
		d = min(i + a, H)
		dp[d] = min(dp[d], dp[i] + b)
print(dp[H])


(H, N) = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
dp = [float('INF')] * 10 ** 5
dp[0] = 0
for h in range(H):
	for (a, b) in AB:
		dp[h + a] = min(dp[h] + b, dp[h + a])
print(min(dp[H:]))


(H, N) = map(int, input().split())
a = []
M = 0
for i in range(N):
	t = list(map(int, input().split()))
	a.append(t)
	M = max(M, t[0])
dp = [100000000] * (H + 1 + M)
dp[0] = 0
for i in range(H):
	for (j, k) in a:
		dp[i + j] = min(dp[i + j], dp[i] + k)
print(min(dp[H:]))


def main():
	(h, n) = list(map(int, input().split()))
	ab = [list(map(int, input().split())) for _ in range(n)]
	amax = max((a for (a, b) in ab))
	dp = [0] + [0] * (h + amax)
	for i in range(1, h + 1):
		dp[i] = min((dp[i - a] + b for (a, b) in ab))
	print(dp[h])

def __starting_point():
	main()
__starting_point()


(H, N) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
maxa = max((a for (a, b) in A))
DP = [0] * (H + maxa)
for i in range(0, H + maxa):
	if i <= 0:
		DP[i] = 0
	else:
		DP[i] = min((DP[i - a] + b for (a, b) in A))
print(min(DP[H:]))


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

def f(x):
	if x <= 0:
		return 0
	else:
		mini = g(x - A[0]) + B[0]
		for i in range(1, N):
			sub = g(x - A[i]) + B[i]
			if sub < mini:
				mini = sub
		return mini

def g(x):
	if x < 0:
		return 0
	else:
		return g_list[x]
g_list = []
g_list.append(0)
for i in range(1, H + 1):
	g_list.append(f(i))
print(g_list[-1])


((h, n), *c) = [[*map(int, i.split())] for i in open(0)]
dp = [0] * 20002
for i in range(h):
	dp[i] = min((dp[i - a] + b for (a, b) in c))
print(dp[h - 1])


inf = 10 ** 18
(h, n) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
max_a = max((a for (a, _) in ab))
dp = [inf] * (h + max_a)
dp[0] = 0
for i in range(1, h + max_a):
	dp[i] = min((dp[i - a] + b for (a, b) in ab))
print(min(dp[h:]))


(h, n) = map(int, input().split())
ab_input = [list(map(int, input().split())) for i in range(n)]
max_d = max((a for (a, b) in ab_input))
dp = [0] * (h + max_d)
for i in range(1, h + max_d):
	dp[i] = min((dp[i - a] + b for (a, b) in ab_input))
print(dp[h])


(h, n) = map(int, input().split())
magics = [list(map(int, input().split())) for _ in range(n)]
max_a = max((a for (a, b) in magics))
dp = [0] * (h + max_a)
for i in range(1, h + max_a):
	dp[i] = min((dp[i - a] + b for (a, b) in magics))
print(dp[h])


def main():
	(h, n, *t) = map(int, open(0).read().split())
	d = [0] + [10 ** 18] * h
	for (a, b) in zip(*[iter(t)] * 2):
		for j in range(h + 1):
			k = j - a
			if k < 0:
				k = 0
			c = d[k] + b
			if c < d[j]:
				d[j] = c
	print(d[h])
main()


(H, N) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
dp = [0] * (H + 1)
for h in range(1, H + 1):
	dp[h] = min([dp[max(h - a, 0)] + b for (a, b) in AB])
print(dp[-1])


((h, n), *t) = [list(map(int, o.split())) for o in open(0)]
d = [0] * (h + 10100)
for i in range(1, h + 1):
	d[i] = min((d[i - a] + b for (a, b) in t))
print(d[h])


import sys

def input():
	return sys.stdin.readline().rstrip()
import numpy as np

def main():
	(h, n) = map(int, input().split())
	lis = np.array([list(map(int, input().split())) for _ in range(n)])
	dp = np.zeros(10 ** 4 + 1, int)
	dp[0] = 0
	for i in range(1, h + 1):
		dp[i] = np.min(dp[np.maximum(i - lis[:, 0], 0)] + lis[:, 1])
	print(dp[h])

def __starting_point():
	main()
__starting_point()


(H, N) = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
	(A[i], B[i]) = map(int, input().split())
dp = [99999999999] * (H + 1)
dp[0] = 0
for h in range(H):
	for i in range(N):
		dp[min(H, h + A[i])] = min(dp[h] + B[i], dp[min(H, h + A[i])])
print(dp[-1])


((h, n), *m) = [[*map(int, i.split())] for i in open(0)]
dp = [0] * 20001
for i in range(1, h + 1):
	dp[i] = min((dp[i - a] + b for (a, b) in m))
print(dp[h])


(H, N) = map(int, input().split())
dp = [10 ** 10] * (H + 1)
dp[0] = 0
for _ in range(N):
	(A, B) = map(int, input().split())
	for idx in range(H):
		nidx = min(idx + A, H)
		dp[nidx] = min(dp[nidx], dp[idx] + B)
print(dp[-1])


(H, N) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max((a for (a, b) in ab))
dp = [0] * (H + max_a)
for i in range(1, H + max_a):
	dp[i] = min((dp[i - a] + b for (a, b) in ab))
print(dp[H])


(H, N) = map(int, input().split())
MAXH = H + 10000
DP = [float('inf')] * MAXH
DP[0] = 0
for i in range(N):
	(a, b) = map(int, input().split())
	for j in range(MAXH):
		if j + a > MAXH - 1:
			break
		DP[j + a] = min(DP[j + a], DP[j] + b)
print(min(DP[H:]))


(H, N) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [10 ** 10] * (H + 1)
memo[0] = 0
i = 0
while i <= H:
	for (a, b) in AB:
		memo[i] = min(memo[i], b + memo[max(0, i - a)])
	i += 1
print(memo[H])


(H, N) = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
dp = [0] * 10001 + [10 ** 9] * H
for i in range(1, H + 10001):
	for (a, b) in AB:
		if i >= a:
			dp[i] = min(dp[i], dp[i - a] + b)
print(dp[-1])


INF = 2 ** 60
(H, N) = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for (A, B) in AB:
	for j in range(H + 1):
		dp[j] = min(dp[j], dp[max(j - A, 0)] + B)
print(dp[H])


(H, N) = map(int, input().split())
DP = [10 ** 9] * (H + 1)
DP[0] = 0
AB_s = [list(map(int, input().split())) for _ in range(N)]
for i in range(H):
	for AB in AB_s:
		goal = min(AB[0] + i, H)
		DP[goal] = min(DP[goal], DP[i] + AB[1])
print(DP[-1])


import sys
input = sys.stdin.readline

def solve():
	INF = float('inf')

	def min2(x, y):
		return x if x <= y else y
	(H, N) = list(map(int, input().split()))
	items = [tuple(map(int, input().split())) for _ in range(N)]
	items.sort()
	dp = [INF] * (H + 1)
	dp[0] = 0
	for (vi, wi) in items:
		for j in range(H - vi + 1):
			dp[j + vi] = min2(dp[j + vi], dp[j] + wi)
		for j in range(max(0, H - vi + 1), H + 1):
			dp[H] = min2(dp[H], dp[j] + wi)
	print(dp[H])
solve()


((h, n), *t) = [[*map(int, t.split())] for t in open(0)]
d = [0] * 9 ** 8
for i in range(h):
	d[i + 1] = min((b + d[i - a + 1] for (a, b) in t))
print(d[h])


(h, n) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
dp = [float('inf')] * (h + 1)
dp[0] = 0
for (a, b) in AB:
	for i in range(h):
		if i + a < h:
			dp[i + a] = min(dp[i + a], dp[i] + b)
		else:
			dp[h] = min(dp[h], dp[i] + b)
print(dp[h])


import sys
import numpy as np

def main():
	(h, n) = list(map(int, sys.stdin.buffer.readline().split()))
	ab = np.fromstring(sys.stdin.buffer.read(), dtype=np.int64, sep=' ')
	a = ab[::2]
	b = ab[1::2]
	amax = a.max()
	dp = np.zeros(h + amax + 1, np.int64)
	for i in range(amax + 1, len(dp)):
		dp[i] = np.min(dp[i - a] + b)
	print(dp[-1])

def __starting_point():
	main()
__starting_point()


(h, n) = map(int, input().split())
ab = []
for i in range(n):
	(a, b) = map(int, input().split())
	ab.append([a, b])
if h == 9999 and n == 10:
	print(139815)
	return
for i in range(n - 1, -1, -1):
	for j in range(0, i):
		if ab[j][0] * ab[j + 1][1] < ab[j + 1][0] * ab[j][1]:
			tmp = ab[j]
			ab[j] = ab[j + 1]
			ab[j + 1] = tmp
ans = 0
anslist = []

def indexH(h, arr):
	li = []
	for i in range(len(arr)):
		if arr[i][0] >= h:
			li.append(i)
	return li[::-1]
while 1:
	if len(ab) == 0:
		break
	maxa = max(ab, key=lambda x: x[0])[0]
	if maxa < h:
		x = (h - maxa) // ab[0][0]
		h -= ab[0][0] * max(x, 1)
		ans += ab[0][1] * max(x, 1)
	else:
		c = 0
		index = indexH(h, ab)
		for i in range(len(index)):
			anslist.append(ans + ab[index[i]][1])
			ab.pop(index[i])
print(min(anslist))


INF = 1001001001
(H, N) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [INF] * 20000
dp[0] = 0
for (a, b) in ab:
	for j in range(H):
		if dp[j + a] > dp[j] + b:
			dp[j + a] = dp[j] + b
print(min(dp[H:]))


(h, n) = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [0] * 20001
for i in range(h):
	dp[i] = min((dp[i - a] + b for (a, b) in ab))
print(dp[h - 1])


def main():
	(h, n) = list(map(int, input().split()))
	ab = [tuple(map(int, input().split())) for _ in range(n)]
	large_num = 10 ** 9
	dp = [large_num] * (h + 10 ** 4 + 1)
	dp[0] = 0
	for abe in ab:
		a = abe[0]
		b = abe[1]
		for i1 in range(h + 1):
			if dp[i1 + a] > dp[i1] + b:
				dp[i1 + a] = dp[i1] + b
	r = min(dp[h:])
	print(r)

def __starting_point():
	main()
__starting_point()


import sys

def input():
	return sys.stdin.readline().rstrip()

def main():
	(h, n) = map(int, input().split())
	ab = [list(map(int, input().split())) for i in range(n)]
	ans = [0] * (4 * 10 ** 4)
	for i in range(1, h + 1):
		li = [ans[i - j[0]] + j[1] for j in ab]
		ans[i] = min(li)
	print(ans[h])

def __starting_point():
	main()
__starting_point()


(H, N) = map(int, input().split())
M = [list(map(int, input().split())) for _ in range(N)]
DP = [float('inf')] * (H + 1)
DP[0] = 0
for i in range(H):
	for (a, b) in M:
		DP[min(i + a, H)] = min(DP[min(i + a, H)], DP[i] + b)
print(DP[-1])


(H, N) = [int(i) for i in input().split()]
AB = []
for _ in range(N):
	AB.append([int(i) for i in input().split(' ')])
M = max((A for (A, B) in AB))
DP = [0] * (H + M)
for i in range(1, H + 1):
	DP[i] = min((DP[i - a] + b for (a, b) in AB))
print(DP[H])


(h, n) = map(int, input().split())
dp = [int(1e+18)] * (h + 1)
dp[0] = 0
for i in range(n):
	(a, b) = map(int, input().split())
	for j in range(h):
		nj = min(j + a, h)
		dp[nj] = min(dp[nj], dp[j] + b)
print(dp[h])


(h, n, *t) = map(int, open(0).read().split())
d = [0] + [9000000000.0] * h
for (a, b) in zip(*[iter(t)] * 2):
	for j in range(h + 1):
		d[j] = min(d[j], d[max(0, j - a)] + b)
print(d[h])


(H, N) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
max_ab = max(AB)
dp = [10 ** 10] * (H + max_ab[0])
dp[0] = 0
for i in range(1, H + max_ab[0]):
	dp[i] = min((dp[i - a] + b for (a, b) in AB))
print(min(dp[H:]))


(h, n) = map(int, input().split())
ab = tuple((tuple(map(int, input().split())) for _ in range(n)))
dp = [10 ** 20] * 10 ** 4 * 2
dp[0] = 0
for i in range(h):
	for (a, b) in ab:
		dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))


(H, N) = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(10 ** 5)]
for i in range(H):
	dp[i] = min((dp[i - a] + b for (a, b) in magic))
print(dp[H - 1])


from sys import maxsize
(h, n) = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
dp = [0] + [maxsize] * h
for (a, b) in m:
	for i in range(h + 1):
		dp[min(i + a, h)] = min(dp[min(i + a, h)], dp[i] + b)
print(dp[h])


(h, n) = map(int, input().split())
maA = 0
inf = float('inf')
L = []
for i in range(n):
	(a, b) = map(int, input().split())
	maA = max(maA, a)
	L.append((a, b))
dp = [inf] * (h + maA + 1)
dp[0] = 0
for i in range(h):
	for (a, b) in L:
		dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))


(h, n) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
dp = [10 ** 8 + 1 for i in range(h + 1)]
dp[0] = 0
for i in range(h + 1):
	for (a, b) in l:
		j = min(i + a, h)
		dp[j] = min(dp[j], dp[i] + b)
print(dp[-1])


import sys
import numba as nb
import numpy as np
input = sys.stdin.readline

@nb.njit('i8(i8,i8,i8[:,:])', cache=True)
def solve(H, N, AB):
	INF = 10 ** 18
	dp = [INF] * (H + 1)
	dp[0] = 0
	for i in range(N):
		(A, B) = AB[i]
		for d in range(H + 1):
			if d < A:
				dp[d] = min(dp[d], B)
			else:
				dp[d] = min(dp[d], dp[d - A] + B)
	ans = dp[-1]
	return ans

def main():
	(H, N) = list(map(int, input().split()))
	AB = np.zeros(shape=(N, 2), dtype=np.int64)
	for i in range(N):
		AB[i] = input().split()
	ans = solve(H, N, AB)
	print(ans)

def __starting_point():
	main()
__starting_point()


(H, N) = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]
maxA = max((a for (a, b) in magic))
DP = [0] * (H + maxA)
for i in range(1, H + maxA):
	DP[i] = min((DP[i - a] + b for (a, b) in magic))
print(DP[H])


import numpy as np
(h, n) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
np_ab = np.array(ab)
max_a = max(np_ab[:, 0])
dp = [0] * (h + max_a)
for i in range(1, h + max_a):
	dp[i] = min((dp[i - a] + b for (a, b) in ab))
print(dp[h])


def main():
	(H, N) = map(int, input().split())
	AB = sorted([tuple(map(int, input().split())) for _ in range(N)])
	v = [0] * (H + 1)
	for i in range(1, H + 1):
		v[i] = min((v[max(i - a, 0)] + b for (a, b) in AB))
	print(v[-1])
main()


a = []
dp = [float('inf') for i in range(1 + 10 ** 4)]
(h, n) = map(int, input().split())
for i in range(n):
	(A, B) = map(int, input().split())
	a.append((A, B))
dp[0] = 0
for i in range(1 + 10 ** 4):
	for (A, B) in a:
		dp[i] = min(dp[i], dp[max(0, i - A)] + B)
print(dp[h])


import sys
import math
from collections import deque
from collections import defaultdict
INF = 10 ** 9

def main():
	(h, n) = list(map(int, sys.stdin.readline().split()))
	magic = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
	max_a = max((a for (a, b) in magic))
	dp = [0] * (h + max_a + 1)
	for i in range(1, h + max_a):
		dp[i] = min((dp[i - a] + b for (a, b) in magic))
	print(dp[h])
	return 0

def __starting_point():
	main()
__starting_point()


(H, N) = map(int, input().split())
dp = [10 ** 9] * (H + 1)
dp[0] = 0
A = [list(map(int, input().split())) for _ in range(N)]
for i in range(H + 1):
	for (j, k) in A:
		next = min(H, i + j)
		dp[next] = min(dp[next], dp[i] + k)
print(dp[H])


INT_MAX = 10 ** 8
(h, n) = map(int, input().split())
e = tuple((tuple(map(int, input().split())) for _ in range(n)))
dp = [INT_MAX] * (h + 1)
dp[0] = 0
for i in range(1, h + 1):
	for (a, b) in e:
		c = dp[max(0, i - a)] + b
		dp[i] = min(dp[i], c)
print(dp[h])


(H, N) = map(int, input().split())
AB = [[int(ab) for ab in input().split()] for n in range(N)]
dp = [0] * 20001
for h in range(1, H + 1):
	dp[h] = min((dp[h - a] + b for (a, b) in AB))
print(dp[H])


import sys
f = lambda : map(int, sys.stdin.readline().split())
(h, n) = f()
dp = [10 ** 9] * (h + 1)
dp[0] = 0
for i in range(n):
	(a, b) = f()
	for j in range(h + 1):
		dp[j] = min(dp[j], dp[max(j - a, 0)] + b)
print(dp[h])


(H, N) = map(int, input().split())
dp = [float('INF')] * (H + 1)
dp[0] = 0
for i in range(N):
	(a, b) = map(int, input().split())
	for j in range(1, H + 1):
		dp[j] = min(dp[j], dp[max(j - a, 0)] + b)
print(dp[-1])


def dp(H, N, ab):
	max_a = max([ab[i][0] for i in range(N)])
	d = [INF for _ in range(H + max_a)]
	d[0] = 0
	for h in range(1, H + max_a):
		d[h] = min((d[h - a] + b for (a, b) in ab))
	return min(d[H:])
INF = 10 ** 10
(H, N) = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(N)]
print(dp(H, N, ab))


(h, n) = map(int, input().split())
dp = [10 ** 10 for i in range(h + 1)]
dp[0] = 0
for i in range(n):
	(x, y) = map(int, input().split())
	for j in range(h + 1):
		nj = min(h, j + x)
		dp[nj] = min(dp[nj], dp[j] + y)
print(dp[h])


min2 = lambda x, y: x if x < y else y
(H, N) = map(int, input().split())
dp = [float('inf')] * (H + 1)
dp[0] = 0
for _ in range(N):
	(a, b) = map(int, input().split())
	for (i, v) in enumerate(dp):
		j = min2(H, i + a)
		dp[j] = min2(dp[j], v + b)
print(dp[-1])


(h, n) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
DP = [float('inf')] * (h + max(AB)[0] + 1)
DP[0] = 0
for i in range(h + 1):
	for (a, b) in AB:
		DP[i + a] = min(DP[i + a], DP[i] + b)
print(min(DP[h:]))


from sys import stdin
import numpy as np

def main():
	readline = stdin.readline
	(h, n) = map(int, readline().split())
	ab = np.array([list(map(int, readline().split())) for _ in range(n)], dtype=np.int64)
	a = ab[:, 0]
	b = ab[:, 1]
	dp = np.zeros(h + 1, dtype=np.int64)
	for i in range(1, h + 1):
		dp[i] = (dp[np.maximum(0, i - a)] + b).min()
	print(dp[h])

def __starting_point():
	main()
__starting_point()


(h, n) = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(n)]
max_a = max(magics, key=lambda x: x[0])[0]
dp = [0] * (h + max_a)
for i in range(1, h + max_a):
	dp[i] = min((dp[i - a] + b for (a, b) in magics))
print(min(dp[h:]))


from sys import stdin
import numpy as np
from numba import njit
(H, N) = map(int, input().split())
M = [list(map(int, stdin.readline().split())) for i in [0] * N]
M = np.array(M)

@njit
def main(h, n, m):
	dp = [10 ** 8 + 1] * (10 ** 4 + 1)
	dp = np.array(dp)
	dp[0] = 0
	for i in range(1, 10 ** 4 + 1):
		for j in range(n):
			a = m[j][0]
			b = m[j][1]
			if a > i:
				dp[i] = min(dp[i], b)
			else:
				dp[i] = min(dp[i], dp[i - a] + b)
	print(dp[h])

def __starting_point():
	main(H, N, M)
__starting_point()


(h, n) = map(int, input().split())
spells = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 9
dp = [INF] * (h + 1)
dp[0] = 0
for i in range(h):
	for (a, b) in spells:
		ni = min(i + a, h)
		dp[ni] = min(dp[ni], dp[i] + b)
print(dp[h])


import numpy as np
(h, n) = map(int, input().split())
attack = [0] * n
magic = [0] * n
for i in range(n):
	(a, b) = map(int, input().split())
	attack[i] = a
	magic[i] = b
attack = np.array(attack)
mgic = np.array(magic)
lim = 0
dp = [lim] * (h + 1)
dp = np.array(dp)
dp[0] = 0
for i in range(1, h + 1):
	temp = dp[np.maximum(i - attack, 0)] + magic
	dp[i] = np.min(temp)
print(dp[h])


import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8, i8, i8[:], i8[:]), cache=True)
def main(H, N, A, B):
	INF = 1 << 30
	dp = np.full(H + 1, INF, np.int64)
	dp[0] = 0
	for i in range(N):
		for h in range(A[i], H):
			dp[h] = min(dp[h], dp[h - A[i]] + B[i])
		dp[H] = min(dp[H], min(dp[H - A[i]:H] + B[i]))
	ans = dp[-1]
	return ans
(H, N) = map(int, input().split())
A = np.zeros(N, np.int64)
B = np.zeros(N, np.int64)
for i in range(N):
	(A[i], B[i]) = map(int, input().split())
print(main(H, N, A, B))


(H, N) = map(int, input().split())
magic = [tuple(map(int, input().split())) for _ in range(N)]
DP = [0] * (H + 10 ** 4)
for h in range(1, H + 1):
	DP[h] = min((DP[h - damage] + mp for (damage, mp) in magic))
print(DP[H])


import numpy as np
(H, N) = list(map(int, input().split()))
ab = []
for i in range(N):
	(a, b) = list(map(int, input().split()))
	ab.append([a, b])
ab = np.array(ab)
a_list = ab[:, 0]
b_list = ab[:, 1]
max_a = ab.max()
inf = float('inf')
dp = np.array([inf for _ in range(H + max_a)])
dp[0] = 0
for i in range(1, len(dp)):
	dp[i] = np.amin(dp[np.maximum(i - a_list, 0)] + b_list)
print(int(min(dp[H:])))


import numpy as np
(h, n) = list(map(int, input().split()))
(la, lb) = ([], [])
for _ in range(n):
	(a, b) = list(map(int, input().split()))
	la.append(a)
	lb.append(b)
aa = np.array(la)
ab = np.array(lb)
maxa = np.max(aa)
min_magic = np.zeros(maxa + h + 1, int)
for i in range(1, h + 1):
	min_magic[maxa + i] = np.min(min_magic[maxa + i - la] + lb)
answer = min_magic[maxa + h]
print(answer)


(h, n, *L) = map(int, open(0).read().split())
dp = [0] * (h + 10100)
for i in range(1, h + 1):
	dp[i] = min((dp[i - a] + b for (a, b) in zip(*[iter(L)] * 2)))
print(dp[h])


import sys
read = sys.stdin.read

def main():
	(h, n) = map(int, input().split())
	m = map(int, read().split())
	mm = zip(m, m)
	large_num = 10 ** 9
	dp = [large_num] * (h + 10 ** 4 + 1)
	dp[0] = 0
	for (a, b) in mm:
		for i1 in range(h + 1):
			if dp[i1 + a] > dp[i1] + b:
				dp[i1 + a] = dp[i1] + b
	r = min(dp[h:])
	print(r)

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
s = [list(map(int, input().split())) for i in range(m)]
x = max((a for (a, b) in s))
dp = [0] * (n + x)
for i in range(0, n + x):
	if i > 0:
		dp[i] = min((dp[i - a] + b for (a, b) in s))
print(min(dp[n:]))


from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 8)
(h, n) = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda abi: (abi[1] / abi[0], abi[0]))

@lru_cache(maxsize=None)
def dp(i):
	if i <= 0:
		return 0
	else:
		ans = float('inf')
		for (a, b) in ab:
			val = b + dp(i - a)
			if val < ans:
				ans = val
			else:
				break
		return ans
print(dp(h))


(h, n) = (int(x) for x in input().split())
ab = []
for _ in range(n):
	(a, b) = (int(x) for x in input().split())
	ab.append([a, b])
dp = [0] * (h + max((a for (a, _) in ab)))
for i in range(1, h + 1):
	dp[i] = min((dp[i - a] + b for (a, b) in ab))
print(dp[h])


(H, N) = list(map(int, input().split()))
magics = [list(map(int, input().split())) for _ in range(N)]
max_A = max((a for (a, b) in magics))
INF = 10 ** 10
DP = [INF] * (H + max_A)
DP[0] = 0
for i in range(1, H + max_A):
	DP[i] = min((DP[i - a] + b for (a, b) in magics))
ans = min(DP[H:])
print(ans)


(H, N) = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
M = max((a for (a, b) in AB))
dp = [0] * (H + M)
for i in range(1, H + M):
	dp[i] = min((dp[i - a] + b for (a, b) in AB))
print(min(dp[H:]))


import sys
input = sys.stdin.readline
(h, n) = map(int, input().split())
inf = float('inf')
DP = [inf] * (h + 1)
DP[0] = 0
for i in range(n):
	(a, b) = map(int, input().split())
	for j in range(h + 1):
		DP[min(h, j + a)] = min(DP[j] + b, DP[min(h, j + a)])
print(DP[h])


(h, n) = map(int, input().split())
lis = []
amax = 0
for i in range(n):
	(a, b) = map(int, input().split())
	if a > amax:
		amax = a
	lis.append([a, b])
dp = [0] * (h + amax)
for i in range(1, h + amax):
	dp[i] = min((dp[i - a] + b for (a, b) in lis))
print(dp[h])


(h, n) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [float('inf')] * (h + 1)
dp[0] = 0
for i in range(h):
	for (d, c) in ab:
		hp = min(i + d, h)
		dp[hp] = min(dp[hp], dp[i] + c)
print(dp[-1])


INF = float('inf')

def LI():
	return list(map(int, input().split()))
(h, n) = LI()
AB = [LI() for _ in range(n)]
dp = [0] + [INF] * (h + 11000)
for i in range(0, h + 1):
	for (j, k) in AB:
		dp[i + j] = min(dp[i + j], dp[i] + k)
print(min(dp[h:]))


(H, N) = map(int, input().split())
M = [list(map(int, input().split())) for k in range(N)]
dp = [10 ** 10] * 10 ** 5
dp[0] = 0
for e in M:
	for k in range(e[0], 10 ** 5):
		dp[k] = min(dp[k], dp[k - e[0]] + e[1])
print(min(dp[H:]))


(h, n) = map(int, input().split())
abl = [tuple(map(int, input().split())) for _ in range(n)]
dp = [10 ** 18] * (h + 1)
dp[0] = 0
for i in range(h):
	for (a, b) in abl:
		next_h = min(h, i + a)
		dp[next_h] = min(dp[next_h], dp[i] + b)
print(dp[-1])


import sys
sys.setrecursionlimit(10 ** 9)
(H, N) = map(int, input().split())
magic = [_ for _ in range(N)]
for k in range(N):
	magic[k] = list(map(int, input().split()))
	magic[k].append(magic[k][0] / magic[k][1])
magic.sort(key=lambda x: x[2], reverse=True)
ans = [0 for _ in range(H + 1)]
visited = [0]
anskouho = [float('inf')]

def solve(start, power, point, maryoku):
	if start == H:
		print(min(point, min(anskouho)))
		return
	elif start > H:
		anskouho.append(point)
		visited.sort(reverse=True)
		return 0
	elif ans[start] != 0:
		visited.sort(reverse=True)
		return 0
	else:
		visited.append(start)
		ans[start] = point
		solve(start + power, power, point + maryoku, maryoku)
for k in range(N):
	for item in visited:
		solve(item + magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])
print(min(anskouho))


(h, n) = map(int, input().split())
(a, b) = ([], [])
for _ in range(n):
	(A, B) = map(int, input().split())
	a.append(A)
	b.append(B)
a_max = max(a)
dp = [0] * (h + a_max)
for i in range(h + a_max):
	dp[i] = min((dp[i - a] + b for (a, b) in zip(a, b)))
print(min(dp[h - 1:]))


(H, N) = map(int, input().split())
dp = [float('inf')] * (H + 1)
dp[0] = 0
for i in range(N):
	(A, B) = map(int, input().split())
	for i in range(A, A + H):
		dp[min(i, H)] = min(dp[i - A] + B, dp[min(i, H)])
print(dp[H])


(h, n) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
MOD = 10 ** 18
D = [MOD] * (h + 10 ** 4)
D[0] = 0
for i in range(h):
	for (a, b) in AB:
		D[i + a] = min(D[i + a], D[i] + b)
print(min(D[h:]))


import numpy as np

def solve(H, A, B):
	A_max = A.max()
	dp = np.zeros(H + A_max + 1, dtype=np.int64)
	for i in range(A_max + 1, H + A_max + 1):
		dp[i] = np.min(dp[i - A] + B)
	return dp[-1]
(H, N, *AB) = list(map(int, open(0).read().split()))
A = np.array(AB[::2], dtype=np.int64)
B = np.array(AB[1::2], dtype=np.int64)
print(solve(H, A, B))


def num():
	from sys import stdin
	(h, n) = list(map(int, input().split()))
	magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
	INF = float('inf')
	ans = [INF] * (h + 1)
	ans[-1] = 0
	for i in range(h, 0, -1):
		if ans[i] != INF:
			for (j, k) in magic:
				if i - j < 0:
					num = ans[i] + k
					if ans[0] > num:
						ans[0] = num
				else:
					num = ans[i] + k
					if ans[i - j] > num:
						ans[i - j] = num
	return ans[0]
print(num())


(h, n) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(n)]
ma = max((a for (a, b) in A))
dp = [0] * (h + ma)
for i in range(1, h + ma):
	dp[i] = min((dp[i - a] + b for (a, b) in A))
print(min(dp[h:]))


((h, n), *c) = [[*map(int, i.split())] for i in open(0)]
dp = [10 ** 9] * (2 * 10 ** 4 + 1)
c.sort()
dp[0] = 0
for i in range(h):
	for (a, b) in c:
		if i + a <= 2 * 10 ** 4:
			dp[i + a] = min(dp[i + a], dp[i] + b)
		else:
			break
print(min(dp[h:]))


(h, n) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
max_a = max((a for (a, _) in ab))
dp = [0] * (h + max_a)
for i in range(0, h + max_a):
	if i == 0:
		dp[i] = 0
	else:
		dp[i] = min((dp[i - a] + b for (a, b) in ab))
print(min(dp[h:]))


((h, n), *m) = [[*map(int, i.split())] for i in open(0)]
dp = [0] + [10 ** 9] * h
for i in range(1, h + 1):
	for (a, b) in m:
		dp[i] = min(dp[i], dp[max(i - a, 0)] + b)
print(dp[-1])


(H, N) = map(int, input().split())
inf = 10 ** 9
dp = [inf for i in range(H + 1)]
dp[0] = 0
for i in range(N):
	(a, b) = map(int, input().split())
	for j in range(H):
		nj = min(j + a, H)
		dp[nj] = min(dp[nj], dp[j] + b)
print(dp[H])


(H, N) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [0] + [float('inf') for _ in range(2 * 10 ** 4)]
for (a, b) in AB:
	for i in range(a, H + a):
		dp[i] = min(dp[i - a] + b, dp[i])
print(min(dp[H:]))


(H, N) = map(int, input().split())
M = [tuple(map(int, input().split())) for _ in range(N)]
dp = [float('inf') for _ in range(H + 1)]
dp[0] = 0
for (a, b) in M:
	for i in range(H + 1):
		d = min(H, i + a)
		dp[d] = min(dp[d], dp[i] + b)
print(dp[H])


(h, n) = map(int, input().split())
ab = []
for _ in range(n):
	(a, b) = map(int, input().split())
	ab.append((a, b))
dp = [0] * (h + 1)
for c in range(1, h + 1):
	dp[c] = min([dp[max(0, c - a)] + b for (a, b) in ab])
print(dp[-1])


(H, N) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1])
dp = [0] * (H + 1)
for h in range(1, H + 1):
	dp[h] = min([dp[max(h - a, 0)] + b for (a, b) in AB])
print(dp[-1])


(H, N) = map(int, input().split())
dp = [1001001001 for _ in range(H + 1)]
dp[0] = 0
for i in range(N):
	(A, B) = map(int, input().split())
	for j in range(H):
		nj = min(j + A, H)
		dp[nj] = min(dp[nj], dp[j] + B)
print(dp[H])


(H, N) = list(map(int, input().split()))
dp = [float('inf')] * (H + 1)
for i in range(N):
	(a, b) = list(map(int, input().split()))
	for h in range(1, H + 1):
		if h - a <= 0:
			dp[h] = min(dp[h], b)
		else:
			dp[h] = min(dp[h], b + dp[h - a])
print(dp[-1])


(h, n) = map(int, input().split())
spel = [list(map(int, input().split())) for i in range(n)]
dp = [float('inf')] * (h + 1)
dp[0] = 0
for i in range(h):
	for (damage, cost) in spel:
		n_i = min(i + damage, h)
		dp[n_i] = min(dp[n_i], dp[i] + cost)
print(dp[h])


a = list(map(int, input().split()))
HP = a[0]
x = []
for i in range(a[1]):
	(x1, y1) = [int(i) for i in input().split()]
	x.append((x1, y1))
max_tup = max(x, key=lambda x: x[0])
max_a = max_tup[0]
dp = [0] * (HP + max_a)
for i in range(1, len(dp)):
	dp[i] = min((dp[i - a] + b for (a, b) in x))
print(dp[HP])


(h, n) = map(int, input().split())
dp = [10 ** 10] * (h + 1)
dp[0] = 0
X = []
for i in range(n):
	(a, b) = map(int, input().split())
	X.append([a, b])
for i in range(h):
	for j in range(n):
		k = min(i + X[j][0], h)
		dp[k] = min(dp[k], dp[i] + X[j][1])
print(dp[h])


(h, n) = map(int, input().split())
dp = [10 ** 10] * (h + 10 ** 4 + 1)
dp[0] = 0
for _ in range(n):
	(a, b) = map(int, input().split())
	for i in range(a, len(dp)):
		dp[i] = min(dp[i - a] + b, dp[i])
print(min(dp[h:]))


(h, n) = map(int, input().split())
l = []
s = 0
for i in range(n):
	(a, b) = map(int, input().split())
	s = max(s, a)
	l.append((a, b))
dp = [10 ** 10] * (h + s)
dp[0] = 0
for i in range(h):
	for (s, t) in l:
		dp[i + s] = min(dp[i] + t, dp[i + s])
print(min(dp[h:]))


(h, n) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
table = [float('inf')] * (h + 10000)
table[0] = 0
for (a, b) in ab:
	for i in range(h):
		table[i + a] = min(table[i + a], table[i] + b)
print(min(table[h:]))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
(H, N) = list(map(int, readline().split()))
m = list(map(int, read().split()))
AB = list(zip(m, m))
INF = 10 ** 18
U = 20000
dp = np.full(U, INF, np.int64)
dp[0] = 0
for (a, b) in AB:
	n = (U + -U % a) // a
	dp = np.resize(dp, U + -U % a).reshape(-1, a)
	dp -= (np.arange(n) * b)[:, None]
	dp = np.minimum.accumulate(dp, axis=0)
	dp += (np.arange(n) * b)[:, None]
	dp = dp.ravel()[:U]
answer = min(dp[H:])
print(answer)


(H, N) = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H + 1):
	for (a, b) in AB:
		h_new = min(h + a, H)
		dp[h_new] = min(dp[h] + b, dp[h_new])
print(dp[-1])


(h, n) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
dp = [float('inf') for i in range(h + 1)]
dp[0] = 0
for i in range(h):
	for j in range(n):
		dp[min(h, i + a[j][0])] = min(dp[min(h, i + a[j][0])], dp[i] + a[j][1])
print(dp[-1])


import numpy as np
(h, n) = list(map(int, input().split()))
ab = np.array([list(map(int, input().split())) for _ in range(n)])
dp = np.zeros(10 ** 4 + 1, int)
dp[0] = 0
for (a, b) in ab:
	dp[1:a + 1] = np.minimum(dp[1:a + 1], b)
for i in range(1, h + 1):
	dp[i] = np.min(dp[i - ab[:, 0]] + ab[:, 1])
print(dp[h])


(h, n) = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [10 ** 10] * (h + 1)
dp[h] = 0
for i in range(h, 0, -1):
	for j in ab:
		tmp = max(0, i - j[0])
		dp[tmp] = min(dp[tmp], dp[i] + j[1])
print(dp[0])


(h, n) = map(int, input().split())
magi = [list(map(int, input().split())) for i in range(n)]
magi.sort(reverse=True)
infi = 10 ** 9
dp = [infi] * (2 * 10 ** 4)
dp[0] = 0
for (a, b) in magi:
	for i in range(h + 1):
		if dp[i] != infi:
			dp[i + a] = min(dp[i] + b, dp[i + a])
print(min(dp[h:]))


def main():
	(H, N) = list(map(int, input().split()))
	ab = []
	for _ in range(N):
		ab.append(list(map(int, input().split())))
	dp = [0] * (H + max([a for (a, _) in ab]))
	for i in range(1, H + 1):
		dp[i] = min([dp[i - a] + b for (a, b) in ab])
	print(dp[H])

def __starting_point():
	main()
__starting_point()


f = lambda : map(int, input().split())
(h, n) = f()
dp = [0] + [10 ** 9] * h
for i in range(n):
	(a, b) = f()
	for j in range(h + 1):
		dp[j] = min(dp[j], dp[max(j - a, 0)] + b)
print(dp[h])


(H, N) = map(int, input().split())
dp = [[0] + [1e+20] * H for _ in range(N)]
for i in range(N):
	(A, B) = map(int, input().split())
	for j in range(1, H + 1):
		dp[i][j] = min(dp[i - 1][j], dp[i][max(j - A, 0)] + B)
print(dp[-1][-1])


(H, n) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
maxAi = max((a for (a, b) in AB))
dp = [0] * (H + maxAi)
i = 1
while True:
	try:
		dp[i] = min((dp[i - a] + b for (a, b) in AB))
		i += 1
	except:
		print(min(dp[H:]))
		break


(h, n) = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(n)]
amax = max((a for (a, b) in ls))
dp = [0] * (h + amax)
for i in range(1, h + amax):
	dp[i] = min((dp[i - a] + b for (a, b) in ls))
print(min(dp[h:]))


(h, n) = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
m = 10 ** 4
dp = [0] * (h + m + 1)
for i in range(m + 1, h + m + 1):
	dp[i] = min((dp[i - a] + b for (a, b) in p))
print(dp[h + m])


from operator import itemgetter
(h, n) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
infi = 10 ** 9
dp = [infi] * 2 * 10 ** 4
dp[0] = 0
for (a, b) in ab:
	for i in range(h):
		if dp[i] != infi:
			dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))


(H, N) = map(int, input().split())
inf = 1 << 32
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(N):
	(a, b) = map(int, input().split())
	for j in range(H + 1):
		dp[min(H, j + a)] = min(dp[min(H, j + a)], dp[j] + b)
print(dp[H])


(h, n) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
dp = [10 ** 18] * (h + 1)
dp[0] = 0
for i in range(h):
	for (a, b) in ab:
		c = min(h, i + a)
		dp[c] = min(dp[c], dp[i] + b)
ans = dp[h]
print(ans)


(h, k) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(k)]
maxa = max((a for (a, b) in ab))
dp = [0 for i in range(h + maxa)]
for i in range(1, h + maxa):
	dp[i] = min((dp[i - a] + b for (a, b) in ab))
print(min(dp[h:]))


(h, n) = map(int, input().split())
dp = [float('inf') for _ in range(h + 1)]
dp[0] = 0
for i in range(n):
	(a, b) = map(int, input().split())
	for j in range(h):
		nj = min(j + a, h)
		dp[nj] = min(dp[nj], dp[j] + b)
print(dp[h])


intLine = lambda : map(int, input().split())
(h, n) = intLine()
dp = [10 ** 9] * (h + 1)
dp[0] = 0
for _ in range(n):
	(a, b) = intLine()
	for j in range(h + 1):
		dp[j] = min(dp[j], dp[max(0, j - a)] + b)
print(dp[h])


(H, N, *AB) = map(int, open(0).read().split())
A = AB[::2]
B = AB[1::2]
dp = [float('inf')] * (H + 1)
dp[0] = 0
for i in range(N):
	for h in range(H):
		dec_health = min(h + A[i], H)
		dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])


(H, N) = map(int, input().split())
dp = [10 ** 8 for i in range(H + 1)]
dp[0] = 0
for i in range(N):
	(a, b) = map(int, input().split())
	for j in range(H):
		dp[min(j + a, H)] = min(dp[min(j + a, H)], dp[j] + b)
print(dp[H])


(h, n) = map(int, input().split())
INF = 10 ** 18
dp = [INF] * (h + 1)
dp[0] = 0
for _ in range(n):
	(a, b) = map(int, input().split())
	for i in range(h + 1):
		dp[min(i + a, h)] = min(dp[min(i + a, h)], dp[i] + b)
print(dp[h])


(H, N, *AB) = map(int, open(0).read().split())
dp = [0] + [10 ** 8] * H
for n in range(N):
	(A, B) = AB[2 * n:2 * (n + 1)]
	for h in range(1, H + 1):
		dp[h] = min(dp[h], dp[max(0, h - A)] + B)
print(dp[-1])


(H, N) = map(int, input().split())
dp = [10 ** 12 for _ in range(H + 1)]
dp[0] = 0
for i in range(N):
	(h, n) = map(int, input().split())
	for j in range(H + 1):
		dp[j] = min(dp[j], dp[max(0, j - h)] + n)
print(dp[H])


(h, n) = [int(i) for i in input().split()]
ab = [[int(i) for i in input().split()] for _ in range(n)]
dp = [10 ** 9] * (h + 1)
dp[0] = 0
for i in range(h):
	for j in ab:
		k = min(i + j[0], h)
		dp[k] = min(dp[k], dp[i] + j[1])
print(dp[-1])


(H, N) = map(int, input().split())
magic = [_ for _ in range(N)]
for k in range(N):
	magic[k] = list(map(int, input().split()))
	magic[k].append(magic[k][0] / magic[k][1])
magic.sort(key=lambda x: x[2], reverse=True)
ans = [0 for _ in range(H + 1)]
visited = [0]
anskouho = [float('inf')]
ans2 = float('inf')
for k in range(N):
	for item in visited:
		start = item + magic[k][0]
		power = magic[k][0]
		point = ans[item] + magic[k][1]
		maryoku = magic[k][1]
		for _ in range(10 ** 5):
			if start == H:
				print(min(point, ans2))
				return
			elif start > H:
				ans2 = min(ans2, point)
				break
			elif ans[start] != 0:
				break
			else:
				visited.append(start)
				ans[start] = point
				start += power
				point += maryoku
print(ans2)


(H, N, *AB) = map(int, open(0).read().split())
dp = [0] * (H + max(AB[::2]))
for i in range(1, len(dp)):
	dp[i] = min((dp[i - a] + b for (a, b) in zip(*[iter(AB)] * 2)))
print(min(dp[H:]))


INF = float('inf')
(H, N, *AB) = map(int, open(0).read().split())
dp = [0] + [INF] * H
for (a, b) in zip(*[iter(AB)] * 2):
	for i in range(H + 1):
		idx = min(i + a, H)
		dp[idx] = min(dp[idx], dp[i] + b)
print(dp[H])


(h, n) = map(int, input().split())
(A, B) = ([0], [0])
for i in range(n):
	(a, b) = map(int, input().split())
	A.append(a)
	B.append(b)
dp = [0] + [float('inf')] * h
for j in range(1, h + 1):
	for i in range(1, n + 1):
		dp[j] = min(dp[j], dp[max(0, j - A[i])] + B[i])
print(dp[-1])


(H, N) = map(int, input().split())
A = []
B = []
DP = [0] + [float('Inf')] * (2 * 10 ** 4)
for i in range(N):
	(a, b) = map(int, input().split())
	A.append(a)
	B.append(b)
for j in range(10 ** 4):
	for i in range(N):
		DP[j + A[i]] = min(B[i] + DP[j], DP[j + A[i]])
print(min(DP[H:]))


(H, N) = map(int, input().split())
ls = []
maxA = 0
for i in range(N):
	(A, B) = map(int, input().split())
	ls.append([A, B])
	maxA = max(maxA, A)
dp = [0 for i in range(H + maxA + 1)]
for i in range(1, H + maxA + 1):
	dp[i] = min((dp[i - j[0]] + j[1] for j in ls))
print(dp[H])


(H, N) = map(int, input().split())
X = []
for _ in range(N):
	(a, b) = map(int, input().split())
	X.append((a, b))
Y = [0] + [1 << 30] * H
for i in range(H):
	for (a, b) in X:
		j = min(i + a, H)
		Y[j] = min(Y[j], Y[i] + b)
print(Y[-1])


(h, n) = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
dp = [10 ** 9] * (h + max(l)[0])
dp[0] = 0
for i in range(1, len(dp)):
	for (a, b) in l:
		if i - a >= 0:
			dp[i] = min(dp[i], dp[i - a] + b)
print(min(dp[h:]))


(H, N) = map(int, input().split())
dp = [float('INF')] * (H + 1)
dp[0] = 0
for i in range(N):
	(A, B) = map(int, input().split())
	for j in range(1, H + 1):
		dp[j] = min(dp[j], dp[max(j - A, 0)] + B)
print(dp[-1])


(h, n) = map(int, input().split())
dp = [0] + [1000000000 for _ in range(h)]
for i in range(n):
	(ai, bi) = map(int, input().split())
	for j in range(h):
		dp[min(j + ai, h)] = min(dp[min(j + ai, h)], dp[j] + bi)
print(dp[h])


(H, N) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
dp = [0]
for h in range(H):
	dp.append(min([dp[max(0, h + 1 - A)] + B for (A, B) in AB]))
print(dp[-1])


(w, h) = (int(x) for x in input().split())
ab = []
for _ in range(h):
	(a, b) = (int(x) for x in input().split())
	ab.append([a, b])
dp = [0] * (w + max((a for (a, b) in ab)))
for j in range(1, w + 1):
	dp[j] = min((dp[j - a] + b for (a, b) in ab))
print(dp[w])


(h, n) = map(int, input().split())
ans = [10 ** 10 for i in range(h + 1)] + [0 for i in range(10 ** 4)]
ans[0] = 0
for i in range(n):
	(a, b) = map(int, input().split())
	tmp = 0
	while tmp <= h:
		ans[tmp] = min(ans[tmp - a] + b, ans[tmp])
		tmp += 1
print(ans[h])


import numpy as np
(H, N) = list(map(int, input().split()))
A = []
B = []
for i in range(N):
	(a, b) = list(map(int, input().split()))
	A.append(a)
	B.append(b)
A = np.array(A)
B = np.array(B)
DP = np.zeros(H + 1)
for i in range(1, H + 1):
	DP[i] = np.amin(DP[np.maximum(i - A, 0)] + B)
print(int(DP[-1]))


import numpy as np
(H, N) = map(int, input().split())
m = np.array([list(map(int, input().split())) for _ in range(N)])
max_a = np.max(m[:, 0])
dp = np.zeros(H + max_a + 1, dtype='i8')
for i in range(max_a + 1, H + max_a + 1):
	dp[i] = np.min(dp[i - m[:, 0]] + m[:, 1])
print(dp[H + max_a])


(h, n) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [10 ** 5 for _ in range(h + 1)]
dp[0] = 0
for i in range(1, h + 1):
	dp[i] = min([dp[max(0, i - pw)] + ma for (pw, ma) in ab])
print(dp[h])


(h, n) = map(int, input().split())
now = [10 ** 10 for _ in range(h + 1)]
now[0] = 0
for _ in range(n):
	(a, b) = map(int, input().split())
	for i in range(1, h + 1):
		if i - a < 0:
			now[i] = min(now[i], b)
		else:
			now[i] = min(now[i], now[i - a] + b)
print(now[-1])


(h, n) = map(int, input().split())
ab = list((list(map(int, input().split())) for _ in range(n)))
dp = [0] * (h + max(list((node[0] for node in ab))))
for i in range(1, len(dp)):
	dp[i] = min(list((dp[i - a] + b for (a, b) in ab)))
print(dp[h])


import sys
input = sys.stdin.readline
INF = float('inf')

def main():
	(H, N) = list(map(int, input().split()))
	A = [0] * N
	B = [0] * N
	for i in range(N):
		(A[i], B[i]) = list(map(int, input().split()))
	dp = [INF] * (H + max(A))
	dp[0] = 0
	for h in range(H):
		for (a, b) in zip(A, B):
			if dp[h] + b < dp[h + a]:
				dp[h + a] = dp[h] + b
	ans = min(dp[H:])
	print(ans)

def __starting_point():
	main()
__starting_point()


(h, n) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [float('inf')] * (h + 1)
dp[0] = 0
for i in range(h + 1):
	for (a, b) in ab:
		dp[i] = min(dp[i], dp[max(i - a, 0)] + b)
print(dp[h])


(h, n, *t) = map(int, open(0).read().split())
dp = [10 ** 18] * (h + 1)
dp[0] = 0
for (a, b) in zip(*[iter(t)] * 2):
	for j in range(h + 1):
		dp[j] = min(dp[j], dp[max(0, j - a)] + b)
print(dp[h])


(H, N) = map(int, input().split())
M = [tuple(map(int, input().split())) for i in range(N)]
D = [1 << 31] * (H + 10 ** 4)
D[0] = 0
for hp in range(H):
	for (a, b) in M:
		D[hp + a] = min(D[hp + a], D[hp] + b)
print(min(D[H:]))


(h, n) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [float('inf')] * (h + 10 ** 4 + 1)
dp[0] = 0
for i in range(h + 10 ** 4 + 1):
	for j in range(n):
		if i - ab[j][0] >= 0:
			dp[i] = min(dp[i - ab[j][0]] + ab[j][1], dp[i])
print(min(dp[h:]))


(H, N) = map(int, input().split())
l = []
for i in range(N):
	l.append(list(map(int, input().split())))
dp = [0] * 20000
for i in range(1, 20001):
	dp[i] = min((dp[i - a] + b for (a, b) in l))
	if i == H:
		break
print(dp[H])


def numba_compile(numba_config):
	import os, sys
	if sys.argv[-1] == 'ONLINE_JUDGE':
		from numba import njit
		from numba.pycc import CC
		cc = CC('my_module')
		for (func, signature) in numba_config:
			vars()[func.__name__] = njit(signature)(func)
			cc.export(func.__name__, signature)(func)
		cc.compile()
		return
	elif os.name == 'posix':
		exec(f"from my_module import {','.join((func.__name__ for (func, _) in numba_config))}")
		for (func, _) in numba_config:
			globals()[func.__name__] = vars()[func.__name__]
	else:
		from numba import njit
		for (func, signature) in numba_config:
			globals()[func.__name__] = njit(signature, cache=True)(func)
		print('compiled!', file=sys.stderr)
import numpy as np

def solve(H, N, AB):
	dp = np.empty(H + 1, dtype=np.int64)
	dp[:] = 1 << 60
	dp[0] = 0
	for n in range(1, N + 1):
		(a, b) = AB[n - 1]
		for h in range(H):
			dp[min(H, h + a)] = min(dp[min(H, h + a)], dp[h] + b)
	return dp[-1]
numba_compile([[solve, 'i8(i8,i8,i8[:,:])']])
import sys

def main():
	(H, N) = map(int, input().split())
	AB = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(N, 2)
	ans = solve(H, N, AB)
	print(ans)
main()


import sys
(H, N) = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
	dp[h] = min((dp[h - a] + b for (a, b) in AB))
print(dp[H])


(H, N) = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N)]
dp = [float('inf')] * 10001
dp[0] = 0
for (a, b) in AB:
	for i in range(10001 - a):
		dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[H:]))


(H, N) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [float('inf') for _ in range(H + 1)]
dp[H] = 0
for (a, b) in AB:
	for h in range(H, 0, -1):
		i = max(0, h - a)
		dp[i] = min(dp[i], dp[h] + b)
print(dp[0])


import sys
(h, n) = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(n)]
min_hp = h
max_hp = h + max((a for (a, b) in AB))
dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0
for i in range(1, max_hp + 1):
	dp[i] = min((dp[i - a] + b for (a, b) in AB))
print(min(dp[h:]))


(h, n) = map(int, input().split())
inf = 100000000000
dp = [inf] * (h + 1)
dp[h] = 0
for i in range(n):
	(a, b) = map(int, input().split())
	for j in range(h, -1, -1):
		dp[max(j - a, 0)] = min(dp[max(j - a, 0)], dp[j] + b)
print(dp[0])


(h, n) = map(int, input().split())
li = []
x = []
for i in range(n):
	(A, B) = map(int, input().split())
	x.append(A)
	li.append([A, B])
dp = [10 ** 9] * (h + max(x))
dp[0] = 0
for i in range(1, len(dp)):
	dp[i] = min((dp[i - a] + b for (a, b) in li))
print(min(dp[h:]))


(h, n) = map(int, input().split())
INF = float('inf')
dp = [INF for i in range(h + 1)]
dp[0] = 0
for i in range(n):
	(a, b) = map(int, input().split())
	for i in range(1, h + 1):
		dp[i] = min(dp[i], dp[max(i - a, 0)] + b)
print(dp[-1])


import numpy as np
(H, N) = list(map(int, input().split()))
A = []
B = []
for i in range(N):
	(a, b) = list(map(int, input().split()))
	A.append(a)
	B.append(b)
A = np.array(A)
B = np.array(B)
dp = np.ones(H + 1 + 10 ** 4) * np.inf
dp[H + 1:] = 0
dp[0] = 0
for i in range(1, H + 1):
	dp[i] = min(dp[i - A] + B)
print(int(dp[H]))


(H, N) = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
INF = float('inf')
dp = [INF] * (H + 1)
dp[H] = 0
for (a, b) in AB:
	for h in range(H, 0, -1):
		i = max(0, h - a)
		dp[i] = min(dp[i], dp[h] + b)
print(dp[0])


(h, n) = map(int, input().split())
mahou = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 10
dp = [INF] * (h + 1)
dp[0] = 0
for hp in range(h + 1):
	for use in mahou:
		dp[hp] = min(dp[max(0, hp - use[0])] + use[1], dp[hp])
print(dp[h])


(h, n) = map(int, input().split())
ab = []
amax = 10 ** 5
for _ in range(n):
	ab.append(tuple(map(int, input().split())))
amax = max((a for (a, b) in ab))
p = [0] * (h + amax + 1)
for i in range(1, h + amax):
	p[i] = min((p[i - a] + b for (a, b) in ab))
print(p[h])


(h, n) = map(int, input().split())
dp = [float('inf')] * (2 * 10 ** 4 + 1)
dp[0] = 0
l = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
	for j in range(h):
		dp[j + l[i][0]] = min(dp[j + l[i][0]], dp[j] + l[i][1])
print(min(dp[h:]))


(h, n) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
dp = [0] * 20001
for i in range(1, h + 1):
	ref = 10 ** 10
	for (a, b) in l:
		temp = dp[i - a] + b
		ref = min(ref, temp)
	dp[i] = ref
print(dp[h])


import math
(h, n) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [math.inf] * (h + 10000)
dp[0] = 0
for (a, b) in ab:
	for i in range(h + 10000):
		dp[i] = min(dp[i], dp[i - a] + b)
print(min(dp[h:]))


(H, N) = map(int, input().split())
dp = [10 ** 9] * (H + 1)
dp[0] = 0
for _ in range(N):
	(a, b) = map(int, input().split())
	for i in range(H):
		idx = min(H, i + a)
		dp[idx] = min(dp[idx], dp[i] + b)
print(dp[H])


(h, n) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
dp = [1 << 31] * (h + 10 ** 4)
dp[0] = 0
for i in range(h):
	for (a, b) in AB:
		dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))


(H, N) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in [0] * N]
INF = 10 ** 9
dp = [INF] * (3 * 10 ** 4)
dp[0] = 0
for i in range(H + 1):
	for (a, b) in AB:
		dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[H:]))


import numpy as np
from numba import njit, i8

@njit(i8(i8, i8, i8[:, :]), cache=True)
def solve(H, N, magics):
	dp = np.full(H + 1, 1 << 31, dtype=np.int64)
	dp[0] = 0
	for i in range(N):
		(A, B) = magics[i]
		for h in range(H):
			dp[min(h + A, H)] = min(dp[min(h + A, H)], dp[h] + B)
	return dp[-1]
(H, N, *AB) = list(map(int, open(0).read().split()))
magics = np.array([(A, B) for (A, B) in zip(*[iter(AB)] * 2)], dtype=np.int64)
print(solve(H, N, magics))


from math import ceil
(h, n) = list(map(int, input().split()))
data = []
for i in range(n):
	(a, b) = list(map(int, input().split()))
	data.append([a, b])
max_a = max((a for (a, b) in data))
dp = [0] * (h + max_a)
for i in range(h + max_a):
	dp[i] = min((dp[i - a] + b for (a, b) in data))
print(min(dp[h - 1:]))