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 heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,n=LI()
a=[]
ab=[]
for i in range(n):
    x,y=LI()
    ab.append((-x,y))
ab.sort()
a=[-i for i,j in ab]
b=[j for i,j in ab]
dp=[[0]+[inf]*(h) for i in range(n+1)]    
dp[0][0]=0

for i in range(n):
    for j in range(h+1):
        dp[i+1][min(h,j+a[i])]=min(dp[i+1][j]+b[i],dp[i+1][min(h,j+a[i])],dp[i][min(h,j+a[i])])

ans=dp[n][h]

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,n=LI()
a=[]
b=[]
for i in range(n):
    x,y=LI()
    a+=[x]
    b+=[y]

dp=[0]+[inf]*h

for i in range(n):
    for j in range(h+1):
        dp[min(h,j+a[i])]=min(dp[j]+b[i],dp[min(h,j+a[i])])

ans=dp[h]

print(ans)

Submission status: Accepted

Solution code:
# import math
# import decimal
# import queue
# import bisect
# import heapq
# import time
# import itertools

mod = int(1e9+7)

def main():
    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 = [int(1e9)] * (h + max(a) + 10)
    dp[0] = 0
    for i in range(n):
        for j in range(1,h+max(a)):
            if a[i] <= j:
                dp[j] = min(dp[j - a[i]] + b[i],dp[j])
    ans = int(1e9)
    for i in range(h,h+max(a)):
        ans = min(ans,dp[i])
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
import queue
import re
import math
import functools


def i_raw():
    return int(input())

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

def is_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


def main():
    H,N = is_raw()
    ABs = [is_raw() for _ in range(N)]
    MA = max([ab[0] for ab in ABs])
    dp = [INF]*(H+MA+1)
    dp[0]=0
    for h in range(1,len(dp)):
        for ab in ABs:
            a,b = ab
            if h < a:
                continue
            dp[h] = min(dp[h],b+dp[h-a])
    return min([dp[h] for h in range(H,len(dp))])


print(main())

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    H, N = map(int, f_i.readline().split())
    
    dp = [10 ** 8] * (H + 10 ** 4)
    dp[0] = 0
    
    for i in range(N):
        A, B = map(int, f_i.readline().split())
        for j, t in enumerate(zip(dp, dp[A:H+A]), start=A):
            dp_i, dp_j = t
            if dp_i + B < dp_j:
                dp[j] = dp_i + B
    
    print(min(dp[H:]))

solve()

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
magic = [0]*(h+1)
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h+1):
        if (magic[j] or j == 0):
            if j == h:
                continue
            key = min([j+a, h])
            if magic[key] == 0:
                magic[key] = magic[j] + b
            else:
                magic[key] = min([magic[key], magic[j]+b])
print(magic[h])

Submission status: Accepted

Solution code:
H,N = list(map(int, input().split()))
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]
 
# dp[damage] := モンスターに damage を与えるために必要な最小コスト
dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)
print(dp[-1])

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
dat = [list(map(int, input().split())) for _ in range(n)]
dp = [[10**9 for _ in range(h+1)] for _ in range(n+1)]
dp[0][h] = 0
for i in range(n):
    for j in range(h, -1, -1):
        dp[i+1][j] = dp[i][j]
        if j + dat[i][0] <= h:
            dp[i+1][j] = min([dp[i+1][j], dp[i+1][j+dat[i][0]]+dat[i][1]])
        if j == 0:
            for k in range(1, min([h, dat[i][0]])+1):
                dp[i+1][j] = min([dp[i+1][j], dp[i+1][k] + dat[i][1]])
print(dp[n][0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)

h,n=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
AB = [tuple(map(int, input().split())) for _ in range(n)]
#効率順にソート
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))

@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float('inf')
        for a, b in AB:
            mp = b + dp(h -a)
            if mp < best:
                best = mp
            else:
                break
        return best

print(dp(h))

Submission status: Accepted

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

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

INF = 10 ** 15
dp = [INF] * H
dp[0] = 0

answer = INF
for a, b in AB:
  for i in range(H):
    if dp[i] != INF:
      if i + a < H:
        dp[i + a] = min(dp[i + a], dp[i] + b)
      else:
        answer = min(answer, dp[i] + b)

print(answer)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A = [0]*N
B = [0]*N

for i in range(N):
    A[i], B[i] = MAP()

dp = [[INF]*(H+max(A)+1) for _ in range(N+1)]
dp[0][0] = 0

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

print(min(dp[N][H:]))

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    
#import numpy as np
#dp = np.zeros([N+1, H+1])
#dp[0, 1:] = np.inf
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(0, N):
    for j in range(1, H+1):        
        dp[i+1][j] = min(dp[i][j], dp[i+1][max(0, j-A[i])] + B[i])
        
print(int(dp[-1][-1]))

Submission status: Accepted

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


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [0] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b if amt - a >= 0 else float('inf') for a, b in magic]

    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)

Submission status: Accepted

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


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [0] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b for a, b in magic]
    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)

Submission status: Accepted

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

def main():
    h,n=map(int,input().split())
    m=0
    AB=[]
    for _ in range(n):
        a,b=map(int,input().split())
        AB.append((a,b))
        m=max(m,a)
    DP=[float('inf')]*(h+m+1)
    DP[0]=0
    for i in range(h+m):
        for a,b in AB:
            if i-a<0:
                continue
            DP[i]=min(DP[i],DP[i-a]+b)
    print(min(DP[h:]))
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
ls = []
m = 0
for i in range(N):
  a, b = map(int,input().split())
  ls += [(a,b)]
  if m<a:
    m = a
dp = [float('inf')]*(H+m+1)
dp[0] = 0
L = H+m+1
ans = float('inf')
for i in range(1,L):
  for j in range(N):
    a, b = ls[j]
    if i-a>=0:
      dp[i] = min(dp[i-a]+b, dp[i])
    if i>=H:
      if ans>dp[i]:
        ans = dp[i]
print(ans)

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/abc153/tasks/abc153_e

個数制限なしDP
一次元の配列を使うパターン。
"""

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)

INF = float('INF')
MAX_J = 10 ** 4 + 1

# DP[j]: ダメージの総和をjにする魔力の最小値
DP = [INF] * MAX_J
DP[0] = 0

# 計算済みのDP[j]にA[i]の魔法を使った場合を計算して、もしそれが最少だったら更新していく

for i in range(N):
    for j in range(MAX_J):
        # nj: 求める添字
        # nj: i番目の魔法を使った後のダメージの総和（Hがmax）
        nj = min(j+A[i], H)
        # DP[nj]はすでに入っている値か、i番目の魔法を使った場合か
        DP[nj] = min(DP[nj], DP[j] + B[i])

print(DP[H])

Submission status: Accepted

Solution code:
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(dp[h])

Submission status: Accepted

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

INF = float('INF')
# MAX_J = (10 ** 4 + 1) * 2
MAX_J = 10 ** 4 + 1

# DP[i][j]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値
DP = [INF] * MAX_J
DP[0] = 0

for i in range(N):
    for j in range(MAX_J):
        # nj: 求める添字
        # nj: i番目の魔法を使った後のダメージの総和（Hがmax）
        nj = min(j+A[i][0], H)
        # DP[nj]はすでに入っている値か、i番目の魔法を使った場合か
        DP[nj] = min(DP[nj], DP[j] + A[i][1])
    # print(i, DP)

print(DP[H])

Submission status: Accepted

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

INF = float('INF')
MAX_J = (10 ** 4 + 1) * 2

# DP[i][j]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値
DP = [INF] * MAX_J
DP[0] = 0

for i in range(N):
    for j in range(MAX_J):
        nj = min(j+A[i][0], H)
        DP[nj] = min(DP[nj], DP[j] + A[i][1])

print(DP[H])

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
magics = sorted(list(map(int, input().split())) for _ in range(n))
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(h+max_cost):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))

Submission status: Accepted

Solution code:
#import numpy as np
import math

H, N = map(int, input().split())
#mahou = np.array([list(map(int, input().split())) for _ in range(N)])
mahou = [list(map(int, input().split())) for _ in range(N)]


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

for h in range(H):
  for d, m in mahou:
    new_hp = min(h + d, H)
    dp[new_hp] = min(dp[new_hp], dp[h] + m)
print(int(dp[-1]))

Submission status: Accepted

Solution code:
def main():
    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 = [0] * (H+max(A))
    for x in range(1, H+1):
        dp[x] = min(dp[x-a] + b for a, b in zip(A, B))

    print(dp[H])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append((a,b))

max_a = max(AB[i][0] for i in range(N))
DP = [10**18 for i in range(H + max_a + 1)]
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:]))

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
magics = []
for n in range(N):
    A, B = map(int, input().split())
    magics.append([A, B])
#print(magics)  
maxa = max(A for A, _ in magics)  
#print(maxa)
point = [0]*(H+maxa)
for i in range(1, H+maxa):
    point[i] = min(point[i-a]+b for a,b in magics)
print(min(point[H:]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

INF = 10**10
def solve(h, n, a, b):
    ab = sorted(zip(a, b), key=lambda _:(_[0]/_[1], -_[0]), reverse=True)
    dp = [-1] * h
    def f(h):
        best = INF
        for x, y in ab:
            if h-x <= 0:
                score = y
            else:
                if dp[h-x] == -1:
                    dp[h-x] = f(h-x)
                score = y + dp[h-x]
            if score < best:
                best = score
            else:
                break
        return best
    return f(h)

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())
print(solve(h, n, a, b))

Submission status: Accepted

Solution code:
import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    H, N = map(int,input().split())
    M = [list(map(int,input().split())) for k in range(N)]

    dp = [10**9 for k in range(10**4+1)]
    dp[0] = 0
    for e in M:
        A, B = e[0], e[1]
        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])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

A = []
B = []

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

X = []

for i in range(H):
	Y = []
	for j in range(N):
		if i+1 <= A[j]:
			Y.append(B[j])
		else:
			Y.append(X[i-A[j]] + B[j])
	
	X.append(min(Y))

print(X[H-1])

Submission status: Accepted

Solution code:
H,N=list(map(int,input().split()))
M=[list(map(int,input().split())) for i in range(N)]
A=[M[i][0] for i in range(len(M))] #AT
B=[M[i][1] for i in range(len(M))] #MP


dp=[0]*(max(A)+H)

for h in range(1,H+1):
    dp[h]=min(dp[h - a] + b for a, b in zip(A,B))  

print(dp[H])

Submission status: Accepted

Solution code:
import sys
Mx = 999999999

H, N = map(int,sys.stdin.readline().split())
L = [list(map(int,sys.stdin.readline().split())) for i in range(N)]

D = [Mx] * 40000

D[0] = 0

for i in range(H+1):
    for spell in L:
        if D[i] + spell[1] < D[i+spell[0]]:
            D[i+spell[0]] = D[i] + spell[1]

sys.stdout.write(str(min(D[H:])))

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
c = [0]*n
m = [0]*n

mc = 0
for i in range(n):
    c[i], m[i] = map(int, input().split())
    if mc < c[i]:
        mc = c[i]
    
dp = [10**10]*(h+mc)
dp[0] = 0

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

Submission status: Accepted

Solution code:
def main():
    h, n = map(int, input().split())
    magic_list = []

    for _ in range(n):
        a, b = map(int, input().split())
        magic_list.append((a, b))

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    # 1-origin
    max_attack = max(magic_list)[0]
    dp = [0] * (h + max_attack)

    # time O(HN)
    for hp in range(1, h + 1):
        dp[hp] = min(dp[hp - attack] + mp for attack, mp in magic_list)

    return dp[h]


main()

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
magic_cost = []
for _ in range(n):
    magic, cost = map(int, input().split())
    magic_cost.append((magic, cost))

dp = [float('infinity')] * h

for i in range(h):
    for j in range(n):
        magic, cost = magic_cost[j]
        if i >= magic:
            dp[i] = min(dp[i], dp[i - magic] + cost)
        else:
            dp[i] = min(dp[i], cost)

print(dp[-1])

Submission status: Accepted

Solution code:
h,n = map(int, input().split())
magic = []
INF = 10**8
dp = [[INF for j in range(h+1)] for i in range(n+1)] #体力がjのモンスターをi番目の魔法までを使って倒せる消費魔力の最小値
 
for i in range(n):
    a,b = map(int, input().split())
    magic.append([a, b])
 
for i in range(n):
    for j in range(h):
        if j+1 > magic[i][0]:
            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j+1-magic[i][0]] + magic[i][1], dp[i+1][j+1-magic[i][0]] + magic[i][1])
        else:
            dp[i+1][j+1] = min(dp[i][j+1], magic[i][1])
            
print(dp[n][h])

Submission status: Accepted

Solution code:
h,n = map(int, input().split())
magic = []
INF = 10**8
 
for i in range(n):
    a,b = map(int, input().split())
    magic.append([a, b])
 
dp = [[INF for j in range(h+1)] for i in range(n+1)] #体力がjのモンスターをi番目の魔法までを使って倒せる消費魔力の最小値
 
for i in range(n):
    for j in range(h):
        if j+1 > magic[i][0]:
            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j+1-magic[i][0]] + magic[i][1], dp[i+1][j+1-magic[i][0]] + magic[i][1])
        else:
            dp[i+1][j+1] = min(dp[i][j+1], magic[i][1])
            
print(dp[n][h])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H,N = [int(i) for i in input().split()]
A = [0] * N
B = [0] * N
for i in range(N) :
    a,b = [int(i) for i in input().split()]
    A[i] = a
    B[i] = b
dp = [[(10**9+7)] * (H+1) for _ in range(N)]
for j in range(H+1):
    if j <= A[0]:
        dp[0][j] = B[0]
    if j > A[0]:
        dp[0][j] = dp[0][j-A[0]] + B[0]
for i in range(1,N):
    for j in range(H+1):
        if j == 0:
            dp[i][j] = min(dp[i-1][0],B[i])
        if j <= A[i]:
            dp[i][j] = min(dp[i-1][j],B[i])
        if j > A[i]:
            dp[i][j] = min(dp[i-1][j],dp[i][j-A[i]]+B[i])
print(dp[N-1][H])

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
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 = [10 ** 18 for _ in range(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:]))

Submission status: Accepted

Solution code:
def main():
  h, n = map(int,input().split())
  magics = []
  for i in range (n):
    a, b = map(int,input().split())
    magics.append([a,b])
  # Using Secondary Array in For Loop
  dp = [0] * (h + max(a for a, b in magics))
  for i in range(1, h + 1):
    dp[i] = min(dp[i - a] + b for a, b in magics)
  print(dp[h])  

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
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.sort(key=lambda ab: (ab[0]/ab[1], -ab[0]), reverse=True)

import sys
sys.setrecursionlimit(100000000)

mem = [-1 for i in range(h)]
def solve(h):
    best = float('inf')
    for a,b in ab:
        if h - a <= 0:
            val = b
        else:
            if mem[h - a] != -1:
                val = b + mem[h - a]
            else:
                mem[h - a] = solve(h - a)
                val = b + mem[h-a]
        if val < best:
            best = val
        else:
            break
    return best

print(solve(h))

Submission status: Accepted

Solution code:
H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
print(min(DP[N-1][H:MAX_A]))

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
#Cost[hp] ... min magic cost if reduced hp is m
cost = [float('inf')] * (H+1)
cost[0] = 0
magics = [tuple(map(int, input().split())) for _ in range(N)]
for hp in range(0, H+1):
    now_cost = cost[hp]
    for a, b in magics:
        reduced_hp = a+hp
        if a + hp > H:
            reduced_hp = H
        cost[reduced_hp] = min(cost[reduced_hp], now_cost+b)
print(cost[H])

Submission status: Accepted

Solution code:
H,N=map(int, input().split())
A=[]
B=[]

dp=[10**10]*(H+1)
dp[0]=0
for n in range(N):
  a,b=map(int, input().split())
  A.append(a)
  B.append(b)
    
for h in range(1,H+1):
  for n in range(N):
    if h-A[n]>=0:
      dp[h]=min(dp[h],dp[h-A[n]]+B[n])
    else:
      dp[h]=min(dp[h],B[n])
print(dp[H])

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
magics = []
for _ in range(N):
  a, b = map(int, input().split())
  magics.append([a, b])
max_a = max(a for a, _ 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(min(dp[H:]))

Submission status: Accepted

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

dp=[float('inf') for i in range(h+10**4+1)] # dp[i]は、総ダメージiの時の最小コスト
dp[0]=0

for i in range(1,h+10**4+1):
    for j in range(n): # 技ループ
        if i>=lis[j][0]:
            dp[i]=min(dp[i],dp[i-lis[j][0]]+lis[j][1])
print(min(dp[h:])) # 総ダメージh以上の最小

Submission status: Accepted

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

dp=[float('inf') for i in range(h+10**4+1)] # dp[i]は、総ダメージiの時の最小コスト
dp[0]=0

for i in range(1,h+10**4+1):
    for j in range(n): # 技ループ
        if i>=lis[j][0]:
            dp[i]=min(dp[i],dp[i-lis[j][0]]+lis[j][1])
#        else:
#            dp[i]=dp[i]
print(min(dp[h:]))

Submission status: Accepted

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

max_da=max(da) 
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for i in range(H+max_da):
    for j in range(N):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

print(min(dp[H:]))

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
AB = []
ma = -1
for _ in range(N):
    a, b = map(int, input().split())
    ma = max(ma, a)
    AB.append([a, b])


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

for h in range(H + 1):
    for a, b in AB:
        dp[h + a] = min(dp[h + a], dp[h] + b)

# print(dp)

ans = inf
for i in range(H, H + ma + 1):
    ans = min(dp[i], ans)

print(ans)

Submission status: Accepted

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

dp=[float('inf') for i in range(h+10**4+1)]
dp[0]=0

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

Submission status: Accepted

Solution code:
import math
import sys
input = sys.stdin.readline
def main():
	H,N = map(int,input().split())
	A,B = [],[]
	ap = A.append
	bp = B.append
	for _ in range(N):
		a,b = map(int,input().split())
		ap(a)
		bp(b)
	
	dp = [[0 for _ in range(H+1)] for _ in range(N)]
	
	for i in range(1,H+1):
		dp[0][i] = math.ceil(i/A[0])*B[0]

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

	print(dp[N-1][H])
if __name__ == '__main__':
	main()