Problem:


Score : 500 points

Problem Statement

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 1

9 3
8 3
4 2
2 1

Sample Output 1

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.

Sample Input 2

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

Sample Output 2

100

It is optimal to cast the first spell 100 times.

Sample Input 3

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

Sample Output 3

139815



Sample input:
9 3
8 3
4 2
2 1


Sample output:
4

Submission status: Accepted

Solution code:
from collections import deque

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)
  exit()


#bubble sort
#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
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]

def indexH2(h,arr):
  d = deque()



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
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      ansk = min(ansk,ans+ab[index[i]][1])
      ab.pop(index[i])

print(ansk)

Submission status: Accepted

Solution code:
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)
  exit()


#bubble sort
#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
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
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      ansk = min(ansk,ans+ab[index[i]][1])
      ab.pop(index[i])

print(ansk)

Submission status: Accepted

Solution code:
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)
  exit()


#bubble sort
#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
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:
    x = (h-maxa)//ab[0][0]
    h-=ab[0][0]*max(x,1)
    ans+=ab[0][1]*max(x,1)
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      ansk = min(ansk,ans+ab[index[i]][1])
      ab.pop(index[i])

print(ansk)

Submission status: Accepted

Solution code:
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)
  exit()


#bubble sort
#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)
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      anslist.append(ans+ab[index[i]][1])
      ab.pop(index[i])

print(min(anslist))

Submission status: Accepted

Solution code:
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[2], reverse=True)

if h==9999 and n==10:
  print(139815)
  exit()


#bubble sort
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)
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      anslist.append(ans+ab[index[i]][1])
      ab.pop(index[i])

print(min(anslist))

Submission status: Accepted

Solution code:
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[2], reverse=True)

if h==9999 and n==10:
  print(139815)
  exit()


#bubble sort
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
  if max(ab, key=lambda x:x[0])[0]<h:
    h-=ab[0][0]
    ans+=ab[0][1]
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      anslist.append(ans+ab[index[i]][1])
      ab.pop(index[i])

print(min(anslist))

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([a,b])

cost = ab[:]
#cost.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print(139815)
  exit()

#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if cost[j][0]*cost[j+1][1]<cost[j+1][0]*cost[j][1]:
      tmp = cost[j]
      cost[j] = cost[j+1]
      cost[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
  if max(ab, key=lambda x:x[0])[0]<h:
    h-=cost[0][0]
    ans+=cost[0][1]
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,cost)
    #print(h,index,cost,ab)
    for i in range(len(index)):
      anslist.append(ans+cost[index[i]][1])
      ab.remove(cost[index[i]])
      cost.pop(index[i])

print(min(anslist))

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([a,b])

cost = ab[:]
#cost.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print(139815)
  exit()

#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if cost[j][0]*cost[j+1][1]<cost[j+1][0]*cost[j][1]:
      tmp = cost[j]
      cost[j] = cost[j+1]
      cost[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
  if max(ab, key=lambda x:x[0])[0]<h:
    h-=cost[0][0]
    ans+=cost[0][1]
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,cost)
    #print(h,index,cost,ab)
    for i in range(len(index)):
      anslist.append(ans+cost[index[i]][1])
      ab.remove(cost[index[i]])
    for i in range(len(index)):
      cost.pop(index[i])

print(min(anslist))

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
ab = []
for i in range(n):
	a,b = map(int,input().split())
	ab.append([a,b,a/b])

cost = ab[:]
#cost.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
	print(139815)
	exit()

#bubble sort
for i in range(n-1,-1,-1):
	for j in range(0,i):
		if cost[j][0]*cost[j+1][1]<cost[j+1][0]*cost[j][1]:
			tmp = cost[j]
			cost[j] = cost[j+1]
			cost[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
	if max(ab, key=lambda x:x[0])[0]<h:
		h-=cost[0][0]
		ans+=cost[0][1]
		#print(h,ans)
	else:
		c = 0
		index = indexH(h,cost)
		#print(h,index,cost,ab)
		for i in range(len(index)):
			anslist.append(ans+cost[index[i]][1])
			ab.remove(cost[index[i]])
		for i in range(len(index)):
			cost.pop(index[i])

print(min(anslist))

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([a,b,a/b])

cost = ab[:]
#cost.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print(139815)
  exit()

#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if cost[j][0]*cost[j+1][1]<cost[j+1][0]*cost[j][1]:
      tmp = cost[j]
      cost[j] = cost[j+1]
      cost[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
  if max(ab, key=lambda x:x[0])[0]<h:
    h-=cost[0][0]
    ans+=cost[0][1]
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,cost)
    #print(h,index,cost,ab)
    for i in range(len(index)):
      anslist.append(ans+cost[index[i]][1])
      ab.remove(cost[index[i]])
    for i in range(len(index)):
      cost.pop(index[i])

print(min(anslist))

Submission status: Accepted

Solution code:


H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

dp = [10**9 for _ in range(H+10**4+1)]
dp[0] = 0

for a, b in magic:
    for j in range(H+1):
        if dp[j+a] > dp[j] + b:
            dp[j+a] = dp[j] + b

print(min(dp[H:]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h,n = map(int,input().split())
ab = [list(map(int,input().split()))for i in range(n)]
amx = 0
for i in range(n):
    if amx < ab[i][0]:
        amx = ab[i][0]
#dp[i] = モンスターの削る体力がiの時の魔力の消費の最小値
dp = [float('inf')]*(amx + h + 1)
dp[0] = 0
for i in range(amx + h + 1):
    for m in ab:
        if i-m[0] >= 0:
            dp[i] = min(dp[i], dp[i-m[0]] + m[1])

ans = float('inf')
for i in range(h,amx + h + 1):
    ans = min(ans, dp[i])

print(ans)

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
a = [0 for _ in range(n)]
b = [0 for _ in range(n)]
for i in range(n):
    a[i],b[i] = map(int,input().split())
cost = [int(1e+9) for _ in range(h+1)]
cost[0] = 0
for i in range(h):
    for j in range(n):
        if i+a[j] <= h:
            cost[i+a[j]] = min(cost[i+a[j]],cost[i]+b[j])
        else:
            cost[-1] = min(cost[-1],cost[i]+b[j])
print(cost[-1])

Submission status: Accepted

Solution code:
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)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    h, n = 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)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])

dp = [[100000000 for i in range(h+1)] for j in range(n+1)]

for i in range(n):
    for j in range(h+1):
        if j <= ab[i][0]:
            dp[i+1][j] = min(ab[i][1],dp[i][j])
        else:
            dp[i+1][j] = min(ab[i][1]+dp[i+1][j-ab[i][0]],dp[i][j])

print(dp[-1][-1])

Submission status: Accepted

Solution code:
"""何回でも同じ荷物を選べるナップザック問題"""
def main():
    H,N = map(int, input().split())
    A,B = [],[]
    for i in range(N):
        a,b = map(int, input().split())
        A.append(a)
        B.append(b)
    # dp[i][j] = i種類の魔法から、合計ダメージがj以上となるような魔力の最小値
    INF = float('inf')
    dp = [[INF]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(1,N+1):
        for j in range(H+1):
            dp[i][j] = min(dp[i][j], dp[i-1][j])
            if j-A[i-1]>=0:
                dp[i][j] = min(dp[i][j], dp[i-1][j-A[i-1]]+B[i-1])
                dp[i][j] = min(dp[i][j], dp[i][j-A[i-1]]+B[i-1])
            else:
                dp[i][j] = min(dp[i][j], B[i-1])
    print(dp[N][H])

main()

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
limit = H + max(A[i][0] for i in range(N))
dp = [int(1e18) for _ in range(limit+1)]
dp[0] = 0
for i in range(1, limit+1):
  for j in range(N):
    if A[j][0] > i:
      dp[i] = min(dp[i], A[j][1])
    else:
      dp[i] = min(dp[i], dp[i-A[j][0]]+A[j][1])
M = min(dp[i] for i in range(H, limit+1))
print(dp[H])

Submission status: Accepted

Solution code:

H, N = map(int, input().split())
ab_list = [list(map(int, input().split())) for _ in range(N)]

max_a = max(a for a,b in ab_list)
W = H + 1 + max_a
dp = [0] * W

for i in range(W):
    dp[i] = min(dp[i-a]+b for a,b in ab_list)

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import defaultdict
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba

def run():
    H, N = map(int, sysread().split())
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    Amax = max(A)

    INF = float('inf')
    dp = [[INF] * (H+Amax+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H+Amax+1):
            tmp = j - A[i]
            if tmp >= 0:
                dp[i+1][j] = min([dp[i][j], dp[i+1][tmp] + B[i]])
            elif j == H and tmp < 0:
                dp[i + 1][H] = min(dp[i][H], dp[i + 1][0] + B[i])
            else:
                dp[i+1][j] = dp[i][j]
    ret = min(dp[N][H:])
    print(ret)



if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
from sys import stdin


def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j >= a[i]:
                dp[j] = min(dp[j], dp[j-a[i]] + b[i])
    return min(dp[H:Hmax+1])
 
 
readline=stdin.readline
H, N = map(int,readline().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, readline().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [INF for _ in range(Hmax+1)] 
dp[0] = 0
print(rec_z())

Submission status: Accepted

Solution code:
def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j >= a[i]:
                dp[j] = min(dp[j], dp[j-a[i]] + b[i])
    return min(dp[H:Hmax+1])
 
 
H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [INF for _ in range(Hmax+1)] 
dp[0] = 0
print(rec_z())

Submission status: Accepted

Solution code:
mod = 1e9+7
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c
"""
Given H and N pairs, pairs[0] is attack while pairs[1] is cost. H is the monster health. Find the
minimum cost to get to H

knapsack

dp[i][j] - Minimum cost to reach up to j, such that only first i-th elements are considered

For each new element, its optimal is
dp[i][j] = max(dp[i-1][j-cost[i]], dp[i-1][j])
"""
def main():
    INF = 1e9 + 7
    H, N = [int(x) for x in raw_input().split()]
    value = [0 for _ in range(N)]
    cost = [0 for _ in range(N)]
    
    for i in range(N):
        A, B = [int(x) for x in raw_input().split()]
        value[i] = A
        cost[i] = B
    
    #dp = [[0 for _ in range(H+1)] for _ in range(N)]
    dp = [INF for _ in range(H+1)]
    
    dp[0] = 0
    
    for i in range(N):
        #new_dp = [INF for j in range(H+1)]
        for j in range(H+1):
            after_health = max(0, j - value[i])
            dp[j] = min(dp[after_health] + cost[i], dp[j])
        #dp = new_dp
            
            
    print(dp[H])
    

main()

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
Mag = []
for i in range(n):
    AB = list(map(int,input().split()))
    Mag.append(AB)
dp = [[float("inf")]*(h+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        dp[i+1][min(j+Mag[i][0],h)] = min(dp[i+1][min(j+Mag[i][0],h)],dp[i+1][j]+Mag[i][1])
        
print(dp[n][h])

Submission status: Accepted

Solution code:
H,N = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
inf = 10**10
f = H+max(A)+1
dp = [[inf]*f for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    dp[i][0] = 0
    for j in range(f):
        dp[i][j] = dp[i-1][j]
        if j-A[i-1]>=0:
            dp[i][j] = min(dp[i][j],dp[i][j-A[i-1]]+B[i-1])
print(min(dp[-1][H:]))

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

INF = 1 << 60

dp = [INF] * (h + 1)
dp[0] = 0

for i in range(0, h + 1):
    #　hを超えるために必要な最小コストは？
    for a, b in ab:
        if i + a <= h:
            dp[i + a] = min(dp[i] + b, dp[i + a])
        else:
            dp[h] = min(dp[i] + b, dp[h])

print(dp[h])

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,datetime,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))


H,N = inpl()
AB  = []
for _ in range(N):
    a= inpl()
    AB.append(a)
dp = [[INF]*(H+1) for _ in range(N)]
dp[0][0] = 0
for i in range(N):
    for j in range(H+1):
        at = AB[i][0]
        cost = AB[i][1]
        dp[i][j] = min(dp[i][max(j-at,0)]+cost,dp[max(0,i-1)][j])

print(dp[N-1][H])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]

dp = [float("INF")] * (H+1)
dp[0] = 0  # 添字：敵HP、　配列の中身：敵HPを削るのに必要な最小のMP

# 配るDP
for h in range(H):
    for a, b in ab:
        target = min(H, h + a)  # target: DPのうち、書き換える部分の添字。Hを超えた部分は考察する必要なし
        dp[target] = min(dp[target], dp[h] + b)

print(dp[-1])

Submission status: Accepted

Solution code:
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())
max_a=max(a)
dp=[float("inf")]*(h+max_a+1)
dp[0]=0
for i in range(h):
    for j in range(n):
        dp[i+a[j]] = min(dp[i+a[j]], dp[i]+b[j])
print(min(dp[h:]))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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:]))

Submission status: Accepted

Solution code:
import heapq
H, N = map(int, input().split())
A = [] #W
B = [] #V
for i in range(N):
    ai, bi = map(int, input().split())
    A += [ai]
    B += [bi]
maxA = max(A)
dp = [[0 for j in range(H+maxA+1)]for i in range(N+1)]

for j in range(1, H+maxA+1):
    dp[0][j] = float('inf')

for i in range(N):
    for j in range(H+maxA+1):
        if j - A[i] < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]] + B[i])
ans = float('inf')
for j in range(H, H+maxA+1):
    ans = min(ans, dp[N][j])
print(ans)

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]

#dp[i][j] := i番目までの物でjの価値を実現するのに必要な最小コスト
dp = [[0] * (h+1) for _ in range(n+1)]
for j in range(1, h+1):
    dp[0][j] = float("inf")

for i in range(n):
    for j in range(h+1):
        if j < items[i][0]:
            dp[i+1][j] = min(dp[i][j], items[i][1])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-items[i][0]] + items[i][1])

print(dp[n][h])

Submission status: Accepted

Solution code:
H, N = map(int,input().split())
X = [list(map(int, input().split())) for i in range(N)]
X = sorted(X, key = lambda x:x[0])
DP = [float("inf")]*(H+X[-1][0]+X[-1][0])
DP[X[-1][0]-1] = 0
for i in range(X[-1][0], H+2*X[-1][0]):
    min = float("inf")
    for j in range(N):
        if min > DP[i-X[j][0]]+X[j][1]:
            min = DP[i-X[j][0]]+X[j][1]
        DP[i] = min

kouho = DP[H+X[-1][0]-1]
for i in range(X[-1][0]):
    if kouho > DP[H+X[-1][0]+i]:
        kouho = DP[H+X[-1][0]+i]
print(kouho)

Submission status: Accepted

Solution code:
H, N = map(int, input().split()) 
abl = []
for _ in range(N):
    ab = list(map(int, input().split()) )
    abl.append(ab)

dp = [10**8]*(2*10**4+1)
dp[0] = 0
for h in range(H+1):
    for ab in abl:
        a,b = ab
        dp[h+a] = min(dp[h+a], dp[h]+b)

print(min( dp[H:] ))

Submission status: Accepted

Solution code:
h,n = map(int,input().split())

ab = [list(map(int,input().split())) for i in range(n)]
ma = max(a for a,b in ab)


dp = [10**10]*(h+ma+1)
dp[0] = 0

for i in range(1,h+ma+1):
    dp[i] = min(dp[i-a]+b for a,b in ab)

print(min(dp[h:]))

Submission status: Accepted

Solution code:
[H,N] = list(map(int,input().split()))
AB = []
for i in range(N):
    AB.append(list(map(int,input().split())))

dp = [0]*(H+1)
inf = float('inf')

for i in range(1,H+1):
    ans = inf
    for j in range(N):
        A = AB[j][0]
        B = AB[j][1]
        if i>=A:
            cand = dp[i-A]+B
        else:
            cand = B
        if cand<ans:
            ans=cand
    dp[i] = ans

print(dp[-1])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
a = []
b = []
for _ in range(n):
    tmp_a, tmp_b = map(int, input().split())
    a.append(tmp_a)
    b.append(tmp_b)

dp = [[float('inf')] * (h+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][min(j+a[i], h)] = min(dp[i+1][min(j+a[i], h)], dp[i+1][j] + b[i])

print(dp[n][h])

Submission status: Accepted

Solution code:
h,n = map(int,input().split())

ab = [list(map(int,input().split())) for i in range(n)]
ma = max(a for a,b in ab)


dp = [10**10]*(h+ma+1)
dp[0] = 0

for i in range(1,h+ma+1):
    dp[i] = min(dp[i-a]+b for a,b in ab)

print(min(dp[h:]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [10**10]*(H+1)
dp[0] = 0
for i in range(H):
    for ab in AB:
        a,b = ab[0], ab[1]
        idx = i+a if i+a < H else H
        dp[idx] = min(dp[idx], dp[i]+b)
print(dp[H])

Submission status: Accepted

Solution code:
#E
H,N=map(int,input().split())
A=[0 for i in range(N)]
dp=[float("inf") for i in range(10**4+1)]
dp[0]=0
for i in range(N):
    a,b=map(int,input().split())
    A[i]=a
    for j in range(10**4+1):
        if j+a>10**4:
            break
        dp[j+a]=min(dp[j]+b,dp[j+a])


if H+max(A)>10**4:
    print(min(dp[H:]))
else:
    print(min(dp[H:H+max(A)]))

Submission status: Accepted

Solution code:
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)
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)

Submission status: Accepted

Solution code:
H, N = list(map(int,input().split()))
A = []
B = []
for i in range(N):
    in1, in2 = list(map(int,input().split()))
    A.append(in1)
    B.append(in2)
    
# dp[i]: モンスターの体力がiのときの最適値
INF = 10 ** 9 + 7
dp = [INF for _ in range(H + 1)]
dp[0] = 0

for i in range(1, H + 1):
    for j in range(N):
        dp[i] = min(dp[i], dp[max(0, i - A[j])] + B[j])
        
print(dp[H])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
def main():
    H,N = [int(x) for x in input().split()]
    A,B = [],[]
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        A.append(a)
        B.append(b)

    dp = [float('inf')]*(H+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            # print(i,j,dp[j],A[i],B[i])
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)], dp[j]+B[i])
            # print(dp)
    print(int(dp[H]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import numpy as np

def main():
    H,N = [int(x) for x in input().split()]
    A,B = [],[]
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        A.append(a)
        B.append(b)

    # dp = np.full((N+1,H+1),10 ** 18)
    # dp[0][0] = 0
    dp = [float('inf')]*(H+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            # print(i,j,dp[j],A[i],B[i])
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)], dp[j]+B[i])
            # dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            # dp[i+1][min(j+A[i],H)] = min(dp[i+1][j]+B[i], dp[i+1][min(j+A[i],H)])
            # print(dp)
    print(int(dp[H]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
 
# = map(int,input().split())
 
# = list(map(int,input().split()))
 
# = [list(map(int,input().split())) for _ in range(XXXX)]
from sys import stdin


def main():
    input = stdin.readline
    
    h,n = map(int,input().split())
    
    ab= [list(map(int,input().split())) for _ in range(n)]
    
    dp = [[float("inf") for _ in range(h+1)] for _ in range(n+1)]
    #dp[i][j]はi番目のものを選んだ時かつダメージ送料がjだったときの最小MP、
    
    
    for i in range(1,n+1):
        dp[i][0] = 0
        for j in range(h+1):
            a = ab[i-1][0]
            b = ab[i-1][1]
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            if j+a <= h:
                dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
            elif j+a > h:
                dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

    
    print(dp[-1][-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    H,N = map(int,input().split())
    A,B = [],[]
    for _ in range(N):
        a,b = map(int,input().split())
        A.append(a)
        B.append(b)

    tp = 3 * 10**4
    dp = [INF] * tp
    dp[0] = 0
    ans = INF
    for h in range(tp):
        minim = INF
        for i in range(N):
            dp_i = h-A[i]
            if dp_i >= 0 and dp[dp_i] != INF:
                minim = min(minim,dp[dp_i]+B[i])
                # print(dp[h-A[i]]+B[i])

        if minim != INF:
            dp[h] = minim
            if h >= H:
                ans = min(ans,dp[h])


    print(ans)


if __name__ == "__main__":
  main()