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,defaultdict,Counter
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from bisect import bisect_left,bisect_right
from math import sqrt,gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode
import sys
sys.setrecursionlimit(10 ** 6)

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse=False):
    data.sort(key=lambda x:x[col],reverse=revese)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def mydictvaluesort(dictionary):
    return sorted( dictionary.items(), key=lambda x:x[1] )

def mydictkeysort(dictionary):
    return sorted( dictionary.items(), key=lambda x:x[0] )

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]

# ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())

h,n = MI()
ab = LI(n)

# dp[i][j]:i番目までの魔法の中から削る体力がj以上になるように選んだ時の消耗魔力の最小値
dp = [ [INF]*(h+1) for _ in range(n+1) ]
dp[0][0] = 0

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

Submission status: Accepted

Solution code:
def main():
    h, n = map(int, input().split())
    INF = 10 ** 9
    dp = [INF for _ in range(2*10**4)]
    AB = [tuple(map(int, input().split())) for _ in range(n)]
    dp[0] = 0
    for a, b in AB:
        for i in range(h):
            dp[i + a] = min(dp[i + a], dp[i] + b)
    print(min(dp[h:]))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INFTY = 10**8
H,N = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
dp = [[INFTY for j in range(H+1)] for i in range(N+1)]
for i in range(N+1):
    dp[i][0]=0
for i in range(1,N+1):
    for j in range(1,H+1):
        dp[i][j] = dp[i-1][j]
        if j<=A[i-1][0]:
            dp[i][j] = min(dp[i][j],A[i-1][1])
        else:
            dp[i][j] = min(dp[i][j],dp[i][j-A[i-1][0]]+A[i-1][1])
print(dp[N][H])

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
h,n = readInts()
A = [readInts() for _ in range(n)]
dp = [INF] * (h+1)
dp[h] = 0
for idx in range(h,-1,-1):
    for i in range(n):
        a,b = A[i]
        dp[max(0,idx-a)] = min(dp[max(0,idx-a)], dp[idx] + b)
print(dp[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit, i8


@njit(i8(i8, i8[:], i8[:]), cache=True)
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 = 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))

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
inf = 1 << 30
dp = [inf] * (h + 1)
dp[h] = 0

for i in range(n):
    for j in range(h, 0, -1):
        nx = max(0, j - ab[i][0])
        dp[nx] = min(dp[nx], dp[j] + ab[i][1])
print(dp[0])

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
AB = []
for _ in range(N):
    A, B = map(int, input().split())
    AB.append([A, B])
dp = [10**9] * (H + 1)
dp[0] = 0
for i in range(H):
    for a, b in AB:
        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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(H, N, AB):
    INF = 10**9
    dp = [INF] * (H + 1)
    dp[H] = 0
    for h in reversed(range(H + 1)):
        for i, (a, b) in enumerate(AB):
            nh = max(0, h - a)
            dp[nh] = min(dp[nh], dp[h] + b)
    print(dp[0])

if __name__ == '__main__':
    input = sys.stdin.readline
    H, N = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    main(H, N, AB)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, M = getNM()
W = []
V = []
for i in range(M):
    a, b = getNM()
    W.append(b)
    V.append(a)

# magicを重複ありで適当に組み合わせて合計Nを目指す
def knapsack_4(N, limit, weight, value):
    dp = [float('inf')] * (limit + 1)
    dp[0] = 0

    for i in range(1, limit + 1):
        for j in range(N):
            if i < value[j]:
                dp[i] = min(dp[i], weight[j])
            else:
                dp[i] = min(dp[i], dp[i - value[j]] + weight[j])
    return dp[-1]
print(knapsack_4(M, N, W, V))

Submission status: Accepted

Solution code:
H,N=map(int,input().split())
AB=[]
for i in range(N):
  AB.append(list(map(int,input().split())))
dp=[10**8]*(H+1)
dp[0]=0
i=0

for i in range(H+1):
  for A,B in AB:
    if i-A>=0:
      dp[i]=min(dp[i-A]+B,dp[i])
  for A,B in AB:
    if i+A>H:
      dp[-1]=min(dp[-1],dp[i]+B)
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
dp=[10000000000]*(10**5+1)
dp[0]=0

a=[]
b=[]
for _ in range(n):
    a1,b1=map(int,input().split())
    a.append(a1)
    b.append(b1)
for i in range(10**4+2):
    
    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:
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+1][h] := i番目の魔法まで見て、ライフをh以上削った時の最小魔力コスト
dp=[[float("inf")]*(H+1) for _ in range(N+1)]

for i in range(N):
	for h in range(H+1):
		if A[i]>=h:
			dp[i+1][h] = min(dp[i][h], B[i])
		else:
			dp[i+1][h] = min(dp[i][h], dp[i+1][h-A[i]]+B[i], dp[i][h-A[i]]+B[i])
print(dp[-1][-1])

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)
#dp[i+1][h] := i番目の魔法まで見て、ライフをh以上削った時の最小魔力コスト
dp=[[float("inf")]*(H+1) for _ in range(N+1)]

for i in range(N):
	for h in range(H+1):
		if A[i]>=h:
			dp[i+1][h] = min(dp[i][h], B[i])
		else:
			dp[i+1][h] = min(dp[i][h], dp[i+1][h-A[i]]+B[i])
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def main():
    H, N = 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])


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
for i in range(h):
    for j in range(n):
        if dp[i] == float('inf'):continue
        next=i+ab[j][0] if i+ab[j][0]<=h else h
        dp[next]=min(dp[next],dp[i]+ab[j][1])
print(dp[-1])

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
for i in range(h):
    for j in range(n):

        next=i+ab[j][0] if i+ab[j][0]<=h else h
        dp[next]=min(dp[next],dp[i]+ab[j][1])
print(dp[-1])

Submission status: Accepted

Solution code:
h, n = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
#(a,b):=(ダメージ,消費魔力)

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

for i in range(h + 1):
    for j in range(n):
        if dp[i] == float('inf'):continue
        temp_a = i + ab[j][0] if i + ab[j][0] < h else h
        temp_b = dp[i] + ab[j][1]

        dp[temp_a] = min(dp[temp_a], temp_b)

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

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)#消費魔力

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

        next=i+a[j] if i+a[j]<=h else h
        dp[next]=min(dp[next],dp[i]+b[j])
print(dp[-1])

Submission status: Accepted

Solution code:
H,N = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N)]
INF = float("inf")
dp0 = [INF]*(H+1)
dp1 = [0]*(H+1)
dp0[0] = 0
for i in range(N):
    a,b = AB[i]
    dp1[H] = dp0[H]
    for h in range(H-1, -1, -1):
        dp1[h] = min(dp0[h], dp1[h+1])
    for h in range(H+1):
        dp1[h] = min(dp1[h], dp1[max(h-a,0)]+b)
    t = dp1
    dp1 = dp0
    dp0 = t
print(dp0[H])

Submission status: Accepted

Solution code:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [[INF] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i, (A, B) in enumerate(AB):
    for j in range(H+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][j] = min(dp[i+1][j], dp[i+1][max(j-A, 0)] + B)
print(dp[N][H])

Submission status: Accepted

Solution code:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [[INF] * (H + 1)] * (N + 1)
dp[0][0] = 0
for i, (A, B) in enumerate(AB):
    for j in range(H+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][j] = min(dp[i+1][j], dp[i+1][max(j-A, 0)] + B)
print(dp[N][H])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,N = map(int,input().split())

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

dp = [[10000000000000]*(H+1) for _ in range(N+1)]

for y in range(N):
    a,b = AB[y]
    for x in range(H+1):
        if x <= a:
            dp[y+1][x] = min(dp[y][x], b)
        else:
            dp[y+1][x] = min(dp[y][x], dp[y+1][x-a]+b)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def main():
  h,n=map(int,input().split())
  dp=[10**9]*(h+1)
  dp[h]=0
  for i in range(n):
    a,b=map(int,input().split())
    for j in range(h,0,-1):
      nxt=j-a
      if nxt<0:
        nxt=0
      if dp[nxt]>dp[j]+b:
        dp[nxt]=dp[j]+b
  print(dp[0])
main()

Submission status: Accepted

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

INF=10**9+7
dp=[INF]*(H+1)
dp[0]=0
for i in range(H):
    if dp[i]==INF:
        continue
    for j in range(N):
        a=A[j][0]
        b=A[j][1]
        k=min(H,i+a)
        dp[k]=min(dp[k], dp[i]+b)
print(dp[-1])

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
inf=float('inf')
dp=[inf]*(h+1)
# dp[i]:ダメージiを与えるための最小魔力
dp[0]=0
for a,b in ab:
  # a:ダメージ,b:魔力
  ndp=[inf]*(h+1)
  ndp[0]=0
  for i in range(1,h+1):
    ndp[i]=min(dp[i],ndp[max(0,i-a)]+b)
  dp=ndp
print(dp[h])

Submission status: Accepted

Solution code:
H,N = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
INFTY = 10**8
dp = [[INFTY for _ in range(H+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(1,N+1):
    for j in range(1,H+1):
        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][0]]+A[i-1][1])
        else:
            dp[i][j] = min(dp[i][j],A[i-1][1])
print(dp[N][H])

Submission status: Accepted

Solution code:
H,N = map(int,input().split());INF = float("inf")
A=[];B=[]
for i in range(N):
  a,b = map(int,input().split())
  A.append(a);B.append(b)
#print(A,B)

dp = [INF for _ in range(H+1)] #dp[i] HPがi残っているときの、魔力の消費最小
dp[H] = 0
for i in reversed(range(H+1)):
  #print(i)
  #print(dp)
  for j in range(N):
    if i - A[j] >= 0:
      dp[i-A[j]] = min(dp[i-A[j]], dp[i] + B[j])
    else:
      dp[0] = min(dp[0], dp[i] + B[j])
ans = dp[0]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


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

for i in range(H+10**4+1):
    for j in range(N):
        if l[j][0] <= i:
            dp[i] = min(dp[i],dp[i-l[j][0]]+l[j][1])

ans = dp[H]
for i in range(1,10**4+1):
    ans = min(ans,dp[H+i])

print(ans)

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

dp = [h * 10 ** 4] * (h + 1)
dp[0] = 0
for i in range(n):
    for j in range(min(a[i], h+1)):
        dp[j] = min(dp[j], b[i])
    for j in range(a[i], h + 1):
        dp[j] = min(dp[j], dp[j - a[i]] + b[i])
print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[5]:


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


# In[12]:


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


# In[ ]:

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

#DP[i] = i までの魔法でモンスターの体力を減らすため消耗する魔力の最小値
dp = [0] * 20001

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

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
M = [tuple(map(int, input().split())) for i in range(N)]
Mmax = max(M, key=lambda x: x[0])[0]
dp = [0 for i in range(H + Mmax + 1)]

for i in range(1, H + 1 + Mmax):
    dp[i] = min(dp[max(0, i - a)] + b for a, b in M)

print(min(dp[H:]))

Submission status: Accepted

Solution code:
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]
#max_a = sorted(magics, key=lambda x: x[0], reverse=True)[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:]))

Submission status: Accepted

Solution code:
h,n = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(n)]
max_a = sorted(magics, key=lambda x: x[0], reverse=True)[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:]))

Submission status: Accepted

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

h,n=map(int,input().split())
magic=[]
for i in range(n):
  magic.append(tuple(map(int,input().split())))

memo={}
def d(hp):
  if hp<=0:
    return 0
  if hp in memo:
    return memo[hp]
  mn=10**10
  for i in magic:
    mn=min(mn,d(hp-i[0])+i[1])
  memo[hp]=mn
  return mn

for i in range(1,h-1):
  d(i)
print(d(h))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

damage=[]
cost=[]
for i in range(n):
  a,b=map(int,input().split())
  damage.append(a)
  cost.append(b)

  
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+damage[i],h)]=min(dp[i+1][min(j+damage[i],h)],dp[i+1][j]+cost[i])


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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
H, N = map(int, input().split())
A = [tuple(map(int, line.split())) for line in sys.stdin.buffer.readlines()]
INF = 1 << 30
dp = [INF]*(H+1)
dp[H] = 0
for i in range(N):
    a, b = A[i]
    for h in range(H, -1, -1):
        x = h-a if h-a > 0 else 0
        if dp[x] > dp[h]+b:
            dp[x] = dp[h]+b
print(dp[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def num():
    from sys import stdin
    h, n = 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())

Submission status: Accepted

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

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

inf = float("inf")
# dp[i][j]:i-1番目までの魔法で体力をj減らした時の消耗魔力の最大値
dp = [[inf]*(h+2) 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+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:
import sys
input = sys.stdin.readline

H, N = map(int, input().split())
AB = [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 AB:
        j = min(H, i+A)
        dp[j] = min(dp[j], dp[i]+B)

print(dp[H])

Submission status: Accepted

Solution code:
import sys, math

input = sys.stdin.readline
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 = [math.inf] * (H+max_a+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:]))

Submission status: Accepted

Solution code:
# E - Crested Ibis vs Monster
INF = 100000000
H,N = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
c = [INF]*H+[0]
for i in range(N):
    A,B = ab[i]
    for h in range(H,0,-1):
        k = max(0,h-A)
        c[k] = min(c[k], c[h]+B)
print(c[0])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h, n = [int(i) for i in input().split()]

magics = [None]


class Magic:
    def __init__(self, attack, cost):
        self.attack = attack
        self.cost = cost


maxA = 0
for i in range(n):
    attack, cost = [int(i) for i in input().split()]
    maxA = max(maxA, attack)
    magics.append(Magic(attack, cost))

dp = [[10 ** 9 for i in range(h + maxA)] for j in range(n + 1)]

for i in range(n + 1):
    for j in range(h + maxA):
        if j == 0:
            dp[i][j] = 0
        elif i == 0:
            continue
        elif j - magics[i].attack >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - magics[i].attack] + magics[i].cost)
        else:
            dp[i][j] = dp[i - 1][j]

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

Submission status: Accepted

Solution code:
H, N = list(map(int, input().split()))
dp = [[float('inf')] * (H + 1)]
dp[0][0] = 0
magic = []
for i in range(N):
  magic.append(list(map(int, input().split())))
  
for i in range(H+1):
  next = dp[i]
  if dp[i][i] != float('inf'):
    for j in magic:
      next[min(H, i + j[0])] = min(dp[i-1][i] + j[1], dp[i][min(H, i + j[0])])
  dp.append(next)

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

Submission status: Accepted

Solution code:
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):
    dp[i] = min(dp[i - a] + b for a, b in l)

print(dp[h])

Submission status: Accepted

Solution code:
H,N = map(int,input().split())
inf = 1000000000
dp = [inf for _ in range(20001)]
magics = []
dp[0] = 0
for i in range(N):
    magic = list(map(int,input().split()))
    magics.append(magic)
for j in range(10001):
    for k in magics:
        dp[j+k[0]] = min(dp[j]+k[1],dp[j+k[0]])
ans = dp[H:]
print(min(ans))

Submission status: Accepted

Solution code:
H, N = list(map(int, input().split()))
A = [[0]*2 for _ in range(N)]
for _ in range(N):
    A[_][0], A[_][1] = list(map(int, input().split()))
# print(A)
# A.sort(key=lambda x: x[1])

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

for i in range(H):
    if dp[i] == INF:
        continue
    for j in range(N):
        a = A[j][0]
        b = A[j][1]
        if i+a >= H:
            dp[H] = min(dp[H], dp[i]+b)
        else:
            dp[i+a] = min(dp[i+a], dp[i]+b)
print(dp[H])

Submission status: Accepted

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

if __name__=="__main__":
    main(H,N,M)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl
import math


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    h, n = MI()
    a = []
    b = []
    for _ in range(n):
        _a, _b = MI()
        a.append(_a)
        b.append(_b)

    max_a = max(a)

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

    for i in range(1, h + max_a + 1):
        min_itr = 10**19

        for j in range(n):
            if i - a[j] > 0:
                min_itr = min(min_itr, dp[i - a[j]] + b[j])

            else:
                min_itr = min(min_itr, b[j])

        dp[i] = min_itr

    print(min(dp[h:h+max_a]))


main()

Submission status: Accepted

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

inf = 10 ** 9
dp = [0] + [inf] * H

for h in range(1, H + 1):
    for n in range(1, N + 1):
        a, b = List[n - 1]
        ref = h - a
        if ref < 0: ref = 0
        dp[h] = min(dp[h], dp[ref] + b)
        

print(dp[H])

Submission status: Accepted

Solution code:
H,N=map(int,input().split())
L=[0]*N
for i in range(N):
    a,b=map(int,input().split())
    L[i]=(a,b)


DP=[float("inf")]*(H+1)
DP[0]=0

for (A,B) in L:
    for k in range(1,H+1):
        if k>=A:
            DP[k]=min(DP[k],DP[k-A]+B)
        else:
            DP[k]=min(DP[k],B)

print(DP[-1])