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:
import math

h,n = map(int,input().split())
a = [] ; b = []
for i in range(n) :
  a1,b1 = map(int,input().split())
  a.append(a1) ; b.append(b1)

#dp[i] = 体力iの敵を倒すのに必要な魔力の最低値
dp = [0,min(b)]

for i in range(2,a[b.index(min(b))]+1) :
  dp.append(min(b))

for i in range(a[b.index(min(b))]+1,h+1) :
  dp.append(10**10)
  for j in range (n) :
    if i-a[j] < 0 :
      dp[i] = min(dp[i],b[j])
      continue
    dp[i] = min(dp[i],dp[i-a[j]]+b[j])

print(dp[h])

Submission status: Accepted

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

INF = 10**10+1

dp = [[INF]*(H+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    dp[i][0] = 0
    A = AB[i-1][0]
    for j in range(1, H+1):
        if j-AB[i-1][0]>=0:
            dp[i][j] = min(dp[i-1][j], dp[i][j-AB[i-1][0]]+AB[i-1][1])
        else:
            dp[i][j] = min(dp[i-1][j], AB[i-1][1])

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

INF = 10**10+1

dp = [[INF]*(H+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    dp[i][0] = 0
    A = AB[i-1][0]
    for j in range(1, H+1):
        if j-AB[i-1][0]>=0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-AB[i-1][0]]+AB[i-1][1], dp[i][j-AB[i-1][0]]+AB[i-1][1])
        else:
            dp[i][j] = min(dp[i-1][j], AB[i-1][1])

print(dp[N][H])

Submission status: Accepted

Solution code:
H,N=map(int,input().split())
lab=[]
maxa=0
for i in range(N):
    a,b=map(int,input().split())
    if a>maxa:
        maxa=a
    lab.append([a,b])
ldp=[10**9 for _ in range(H+maxa)]
ldp[0]=0
for i in range(1,H+maxa):
    ldp[i]=min(ldp[i-a]+b for a,b in lab)
print(min(ldp[H:]))

Submission status: Accepted

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

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

for i in range(H+max(A)) :
    for j in range(N) :
        if i >= A[j] :
            dp[i] = min(dp[i], dp[i-A[j]]+B[j])
    if dp[i] == 10**10 :
        dp[i] = min(B)

print(min(dp[H:H+max(A)]))

Submission status: Accepted

Solution code:
H,N = map(int,(input().split()))
dp = [10**9]*(H+1)
dp[0] = 0

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

for i in range(H+1):
    for j,k in A:
        next = min(H,i+j)
        dp[next] = min(dp[next],dp[i]+k)

print(dp[H])

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
dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        temp = i - a
        if temp < 0:
            temp = 0
        need_magic = dp[temp] + b
        if need_magic < dp[i]:
            dp[i] = need_magic
        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print(dp[-1])

Submission status: Accepted

Solution code:
h,n = [int(x) for x in input().split()]
d = []
mp = []
for _ in range(n):
    a,b = [int(x) for x in input().split()]
    d.append(a)
    mp.append(b)
ma = max(d)
dp = [[float("inf")]*(h+ma) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(h+ma):
        if j<d[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j-d[i]]+mp[i])
    
ans = dp[n][h:h+ma+1]
print(min(ans))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
L=[]
maA=0
inf=float("inf")
for i in range(n):
      a,b=map(int,input().split())
      L.append((a,b))
      maA=max(maA,a)

dp=[inf]*(h+maA+1)
dp[0]=0
for i in range(h):
      for j in L:
            dp[i+j[0]]=min(dp[i+j[0]],dp[i]+j[1])
      
print(min(dp[h:]))

Submission status: Accepted

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

inf = 10 ** 18
d = [inf] * (h+1)

d[h] = 0
for i in reversed(range(h+1)):
    for a, c in m:
        if d[i] != inf:
            d[max(0, i-a)] = min(d[max(0, i-a)], d[i] + c)

print(d[0])

Submission status: Accepted

Solution code:
H,n = map(int,input().split())
ab = []
mb = 0 #max of b
for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b])
    mb = max(mb,b)
inf = 10**9+7

dp = [inf]*(H+mb+1) #dp[h]は敵のhpをちょうどhだけ減らすのに必要な最小コスト
dp[0] = 0
for h in range(H+mb+1):
    for a,b in ab:#dp[h]を更新するときに最小となる魔法a,bを選ぶ
        if h >= a:
            dp[h] = min(dp[h-a]+b,dp[h])
        else:
            pass
ans = inf
for h in range(H,H+mb+1):
    ans = min(dp[h],ans)
print(ans)

Submission status: Accepted

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

INF = 10**10
dp = [INF] * (h + 1)
dp[h] = 0
for i in reversed(range(h + 1)):
    for aj, bj in magic:
        dp[max(0, i - aj)] = min(dp[max(0, i - aj)], dp[i] + bj)

print(dp[0])

Submission status: Accepted

Solution code:
#int でsplitを使う場合はmap関数を利用しなければならない
H,N = map(int,input().split())
li=[]
x=[]
for i in range(N):
    A,B = map(int,input().split())
    x.append(A)
    li.append([A,B])
dp = [10**9]*(H+max(x))
dp[0] = 0
for i in range(1,len(dp)):
    dp[i] = min(dp[i-a] + b for a,b in li)
print(min(dp[H:]))

Submission status: Accepted

Solution code:
import numpy as np

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

a = ab[:, 0]
b = ab[:, 1]

dp = np.zeros(10**5, dtype=np.int)

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

print(dp[h])

Submission status: Accepted

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

A=[]
B=[]

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

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

    A.append(a)
    B.append(b)

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

Submission status: Accepted

Solution code:
from math import ceil

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

"""
ナップサック問題の典型類題。
dp[i][j] = (magicを0〜i番目まで用いて体力jのモンスターを倒すのに必要なmpの最小値)
とすると、
    dp[i][j] = min(dp[i-1][j], dp[i][j-a_i] + b_i)
これでdpテーブルは全部埋められる。
"""

dp = [[float("inf")] * (H + 1) for _ in range(N)]
# まずは初期化
for i in range(N):
    dp[i][0] = 0
for j in range(H + 1):
    a0, b0 = magic[0]
    dp[0][j] = b0 * ceil(j / a0)

# ここからdp
for i in range(1, N):
    for j in range(1, H + 1):
        a, b = magic[i]
        if j - a < 0:
            dp[i][j] = min(dp[i - 1][j], b)
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-a] + b)

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

Submission status: Accepted

Solution code:
# DP[i][j] = i番目まででjの体力を減らせる場合の最小の魔力消費

h, n = map(int, input().split())
a, b= [0]*n, [0]*n
for i in range(n):
    aa, bb = map(int, input().split())
    a[i], b[i] = aa, bb

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

print(dp[n][h])

Submission status: Accepted

Solution code:
"""
dp[与えたダメージ] = 使用した魔力
"""
h, n = map(int, input().split())
attacks = []
INF = 10000000000000
dp = [INF for _ in range(h + 1)]
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    attacks.append([a, b])
    
for i in range(h):
    for j in range(n):
        dp[min(h,i + attacks[j][0])] = min(dp[min(h, i + attacks[j][0])], dp[i] + attacks[j][1])
print(dp[h])

Submission status: Accepted

Solution code:
#動的計画法
import numpy as np
H, N = map(int, input().split())

A=np.empty(N,dtype=int)
B=np.empty(N,dtype=int)
for i in range(N):
    A[i],B[i]=map(int,list(input().split(" ")))

DP=np.empty(H+1,dtype=int)

def battle(hp,magic=0):
  #print(hp,magic)
  if hp==0:
    return magic
  t = hp-A
  t[t<0] = 0
  min_power = min(DP[t]+B)
  return magic+min_power

#DP = [0]*(H+1)
for i in range(H+1):
  DP[i] = battle(i)
  #print(DP[i])
ans = DP[H]
print(ans)

#print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import numpy as np
h, n = map(int, input().split())
ab = np.array([np.fromstring(input(), dtype=np.int64, sep=" ") for _ in range(n)])

a = ab[:, 0]
b = ab[:, 1]

dp = np.zeros(10**6, dtype=np.int)

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

print(dp[h])

Submission status: Accepted

Solution code:
import numpy as np
h, n = map(int, input().split())
ab = np.array([np.fromstring(input(), dtype=np.int64, sep=" ") for _ in range(n)])

a = ab[:, 0]
b = ab[:, 1]

dp = np.zeros(10**6, dtype=np.int)

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

print(dp[h])

Submission status: Accepted

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

a = ab[:, 0]
b = ab[:, 1]

dp = np.zeros(10**8, dtype=np.int)

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

print(dp[h])

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(N)]
inf = 10 ** 9 + 1

"""
dp[h]: hの攻撃を与える際の、最小魔力消費量
"""
dp = [inf] * (H + 1 + 10**4)
dp[0] = 0

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

print(min(dp[H:]))

Submission status: Accepted

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

INF = int(1e18)
dp = [INF] * (H + 1)
dp[H] = 0;
for i in range(N):
    for j in range(H, -1, -1):
        dp[max(0, j - A[i][0])] = min(dp[max(0, j - A[i][0])], dp[j] + A[i][1])

ans = dp[0]
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
H,N=map(int,input().split())
l=[1000000000]*(H+1)
l[0]=0
for i in range(N):
    A,B=map(int,input().split())
    for j in range(1,min(A+1,H+1)):
        if l[j]>B:
            l[j]=B
    for j in range(H):
        if j+A<=H:
            if l[j]+B<l[j+A]:
                l[j+A]=l[j]+B
print(l[-1])

Submission status: Accepted

Solution code:
def main():
    H, N = map(int, input().split())
    dam, mp = [0] * N, [0] * N
    for i in range(N):
        dam[i], mp[i] = map(int, input().split())

    # dp[i magic][j damage] := min mp
    H_MAX = H + max(dam)
    INF = float('inf')
    dp = [[INF] * (H_MAX + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H_MAX + 1):
            if j - dam[i] >= 0:
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - dam[i]] + mp[i])
            else:
                dp[i + 1][j] = dp[i][j]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
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
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
L = [LIST() for i in range(N)]
A = []
B = []
for a, b in L:
    A.append(a)
    B.append(b)

v = H + max(A)

dp = [[INF] * (v + 1) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(v):
        if j-A[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j-A[i]]+B[i], dp[i][j])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

# for i in range(1, N+1):
#     for j in range(1, v+1):
#         if j-A[i-1] >= 0:
#             # i
#             dp[i][j] = min(dp[i-1][j-A[i-1]]+B[i-1], dp[i][j])
#         dp[i][j] = min(dp[i-1][j], dp[i][j])

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

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,n=LI()
  w=[]
  v=[]
  max_w=0
  for _ in range(n):
    _w,_v=LI()
    w.append(_w)
    v.append(_v)
    max_w=max(max_w,_w)

  dp=[[inf]*(h+10**4+1) for _ in range(n+1)]
  dp[0][0]=0
  for i in range(n):
    for j in range(h+max_w):
      if j<w[i]:
        dp[i+1][j]=dp[i][j]
      else:
        dp[i+1][j]=min(dp[i][j],dp[i+1][j-w[i]]+v[i])
  ans=inf
  for i in range(n+1):
    for j in range(h,h+max_w):
      ans=min(ans,dp[i][j])

  return ans

# main()
print(main())

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

dp = [[0 for _ in range(H+1)] for _ in range(N+1)]
for j in range(H+1):
    dp[0][j] = float("inf")
#print(*dp, sep="\n")
for i in range(1,N+1):
    for j in range(1,H+1):
        #print(i,j)
        dp[i][j] = min(dp[i-1][j], dp[i][max(j-A[i-1],0)]+B[i-1])

#print(*dp, sep="\n")
print(dp[N][H])

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
inf = 10**11

# dp[i]: 体力iを減らす魔力の最小値
dp = [inf] * 20000
dp[0] = 0

for _ in range(n):
    a, b = map(int, input().split())
    for j in range(h):
        dp[j+a] = min(dp[j] + b, dp[j+a])

print(min(dp[h:]))

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    H,N = LMIIS()
    AB = XLMIIS(N)
    #最小消費量[価値]
    inf_v = 20000
    inf_c = 10**8
    dp = [inf_c]*inf_v
    dp[0] = 0
    max_c = 0
    for i in range(H):
        if dp[i] == inf_c:
            continue
        for a,b in AB:
            dp[i+a] = min(dp[i+a], dp[i] + b)
            max_c = max(max_c,i+a)
    print(min(dp[H:max_c+1]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    H,N = LMIIS()
    AB = XLMIIS(N)
    #最小消費量[価値]
    inf_v = 20000
    inf_c = 10**8
    dp = [inf_c]*inf_v
    dp[0] = 0

    for i in range(H):
        if dp[i] == inf_c:
            continue
        for a,b in AB:
            dp[i+a] = min(dp[i+a], dp[i] + b)
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

inf = 10 ** 9
max_h = 2 * 10**4 + 10
dp = [inf] * max_h
dp[0] = 0
for a, b in ab:
    for i in range(max_h - a + 1):
        dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[h:]))

Submission status: Accepted

Solution code:
INF = 1000000000

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

maxA = max(AB, key=lambda x: x[0])[0]

dp = [INF for i in range(h+maxA)]
dp[0] = 0

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

print(min(dp[h:]))

Submission status: Accepted

Solution code:
import numpy as np
H,N=map(int,list(input().split(" ")))
a=np.empty(N,dtype=int)
b=np.empty(N,dtype=int)
for i in range(N):
    a[i],b[i]=map(int,list(input().split(" ")))
dp=np.empty(H+1,dtype=int)
dp[0]=0
for h in range(1,H+1):
    t=h-a
    t[t<0]=0
    dp[h]=np.min(dp[t]+b)
print(dp[H])

Submission status: Accepted

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

Submission status: Accepted

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

print(dp[h])

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
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
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
L = [LIST() for i in range(N)]

A = []
B = []
for a, b in L:
    A.append(a)
    B.append(b)

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

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

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




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

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

Submission status: Accepted

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

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for x in range(1, H + max_damage):
    dp[x] = min(dp[x - damage] + cost for damage, cost in magic)
    
ans = min(dp[H:])

print(ans)

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:
import numpy as np
H,N = map(int,input().split())

a = np.empty(N,dtype='int')
b = np.empty(N,dtype='int')

# dp[i] ヒットポイントiの魔物を倒すのに必要な最小の魔力
dp = np.array([float('inf')]*(H+1))
dp[0] = 0

for i in range(N):
    a[i],b[i] = map(int,input().split())

# hがヒットポイント
for h in range(1,H+1):
    t = h - a
    t[t<0] = 0
    dp[h] = np.min(dp[t] + b)

print(int(dp[H]))

Submission status: Accepted

Solution code:
import math
 
h,n=map(int,input().split())
a=[0]*n
b=[0]*n
for i in range(n):
    a[i],b[i]=list(map(int,input().split()))
 
 
dp=[[0 for j in range(h+1)] for i in range(n)]
for j in range(h+1):
    dp[0][j]=math.ceil(j/a[0])*b[0]
for i in range(n-1):
    for j in range(h+1):
        if j<a[i+1]: dp[i+1][j]=min(dp[i][j],b[i+1])
        else:dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i+1]]+b[i+1])
print(dp[n-1][h])

Submission status: Accepted

Solution code:
import math

h, n = map(int, input().split())
a = [0] * n
b = [0] * n
#print(a, b)
for i in range(n):
    a[i], b[i] = map(int, input().split())

#print(a)
#print(b)
INF = int(1e10)
dp = [[INF] * (h+1) for i in range(n+1)]
for i in range(h+1):
    dp[0][i] = math.ceil(i / a[0]) * b[0]
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    for j in range(h+1):
        if j < a[i]:
            dp[i+1][j] = min(math.ceil(j / a[i]) * b[i], dp[i][j])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j - a[i]] + b[i])
#print(dp)
print(dp[n][h])

Submission status: Accepted

Solution code:
import math

h, n = map(int, input().split())
a = [0] * n
b = [0] * n
#print(a, b)
for i in range(n):
    a[i], b[i] = map(int, input().split())

#print(a)
#print(b)
INF = int(1e10)
dp = [[INF] * (h+1) for i in range(n+1)]
for i in range(h+1):
    dp[0][i] = math.ceil(i / a[0]) * b[0]
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    for j in range(h+1):
        if j < a[i]:
            dp[i+1][j] = min(-(-j // a[i]) * b[i], dp[i][j])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j - a[i]] + b[i])
#print(dp)
print(dp[n][h])

Submission status: Accepted

Solution code:
import math

h, n = map(int, input().split())
a = [0] * n
b = [0] * n
#print(a, b)
for i in range(n):
    a[i], b[i] = map(int, input().split())

#print(a)
#print(b)
INF = int(1e10)
dp = [[INF] * (h+1) for i in range(n+1)]
for i in range(h+1):
    dp[0][i] = math.ceil(i / a[0]) * b[0]
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    for j in range(h+1):
        if j < a[i]:
            dp[i+1][j] = min(-(-j // a[i]) * b[i], dp[i][j])
        else:
            dp[i+1][j] = min(-(-j // a[i]) * b[i], dp[i][j], dp[i+1][j - a[i]] + b[i])
#print(dp)
print(dp[n][h])

Submission status: Accepted

Solution code:
#E
h,n=map(int,input().split())
a=[]
#複数行　複数列入力listA
for i in range(n):
    a.append(list(map(int,input().split())))
s=[]
max_a=max(a for a,b in a)
dp=[10**18 for i 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 a)
print(min(dp[h:]))

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 = [0] * H

for i in range(H):
    minM = float('inf')
    for j in range(N):
        if i+1 - A[j] >= 0:
            M = DP[i-A[j]] + B[j]
        else:
            M = B[j]
        if minM > M:
            minM = M
    DP[i] = minM

print(int(DP[H-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
H, N = (int(i) for i in input().split())  

a = np.empty(N, dtype='int')
b = np.empty(N, dtype='int')
dp = np.array([float('inf')]*(H+1))
dp[0] = 0

for i in range(N):
  a[i], b[i] = map(int, input().split())
  
for i in range(1, H+1):
  i_from = i - a
  i_from[i_from<0] = 0
  dp[i] = np.min(dp[i_from] + b)
print(int(dp[H]))

Submission status: Accepted

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

for i in range(N):
    A, B = map(int, input().split())
    Magic.append((A, B))

HP = [10**9] * (H+1)
HP[0] = 0

for m in Magic:
    if m[0] >= H:
        HP[H] = min(HP[H], HP[0] + m[1])
    else:
        HP[m[0]] = min(HP[m[0]], HP[0] + m[1])

for i in range(1, H+1):
    if HP[i]:
        for m in Magic:
            if i + m[0] >= H:
                HP[H] = min(HP[H], HP[i] + m[1])
            else:
                HP[i + m[0]] = min(HP[i + m[0]], HP[i] + m[1])
print(HP[H])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve():
    H, N = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    
    INF = 10 ** 9
    dp = [INF for _ in range(10 ** 7)]
    dp[0] = 0

    for a, b in A:
        for i in range(H+1):
            if dp[i] == INF: continue
            dp[i+a] = min(dp[i+a], dp[i] + b)
            
    return min(dp[H:])

print(solve())

Submission status: Accepted

Solution code:
import numpy as np
max_hp, n_magic = map(int, input().split())
power = np.empty(n_magic, dtype='int')
mp = np.empty(n_magic, dtype='int')
for i in range(n_magic):
    power[i], mp[i] = map(int, input().split())

hp_gauge = np.array([float('inf')] * (max_hp+1))
hp_gauge[0] = 0

for remaining_hp in range(1, max_hp+1):
    pre_turn_hp = remaining_hp - power
    pre_turn_hp[pre_turn_hp < 0] = 0
    hp_gauge[remaining_hp] = np.min(hp_gauge[pre_turn_hp] + mp)
    
print(int(hp_gauge[max_hp]))

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())
a= [list(map(int, input().split())) for i in range(n)]

dp=[float('inf')]*(h+1)
dp[0]=0
for i in range(n):
    x=a[i][0]
    y=a[i][1]
    for j in range(h+1):
        if j>=x:
            dp[j]=min(dp[j-x]+y,dp[j])
        else:
            dp[j]=min(y,dp[j])

print(dp[-1])

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
a_list = []
b_list = []
for i in range(n):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
    
dp=[[float('inf') for i in range(h+1)]for i in range(n+1)]#i番めの魔法までを使って体力j減らすのに必要な魔力の最小値
dp[0][0]=0

for i in range(1,n+1):
  for j in range(h+1):
    if j>=a_list[i-1]:
      ai=a_list[i-1]
      bi=b_list[i-1]
      dp[i][j]=min(dp[i][j-ai]+bi,dp[i-1][j])
    else:
      dp[i][j]=min(dp[i-1][j],b_list[i-1])
ans=dp[n][h]
print(ans)

Submission status: Accepted

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

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

for i in range(n):
    dmg=s[i][0]
    mp=s[i][1]
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        dp[i+1][min(j+dmg,h)] = min(dp[i+1][min(j+dmg,h)], dp[i+1][j]+mp)

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=[[10**9 for i in range(H+1)] for j 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(H,j+A[i])],dp[i+1][j]+B[i])
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def calc():
  import numpy as np
  h,n = map(int,input().split())
  a = np.zeros(n,np.int)
  b = a.copy()
  for i in range(n):
      a[i],b[i] = map(int,input().split())


  attack_max = np.max(a)
  majik_min = min(b)
  dp = np.zeros(h+attack_max,np.int)

  for i in range(1,len(dp)):
      c = dp[i-a[i-a>=0]]
      e = i-a[i-a>=0]
      d = c[(c!=0)+(e==0)]+b[i-a>=0][(c!=0)+(e==0)]
      if len(d)>0:
          dp[i] = np.min(d)

  print(np.min(dp[h:][dp[h:]>0]))
  
calc()

Submission status: Accepted

Solution code:
import numpy as np
h,n = map(int,input().split())
a = np.zeros(n,np.int)
b = a.copy()
for i in range(n):
    a[i],b[i] = map(int,input().split())
    

attack_max = np.max(a)
majik_min = min(b)
dp = np.zeros(h+attack_max,np.int)

for i in range(1,len(dp)):
    c = dp[i-a[i-a>=0]]
    e = i-a[i-a>=0]
    d = c[(c!=0)+(e==0)]+b[i-a>=0][(c!=0)+(e==0)]
    if len(d)>0:
        dp[i] = np.min(d)
    
print(np.min(dp[h:][dp[h:]>0]))

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
AB=[]
maA=0
inf=float("inf")
for i in range(n):
   a,b=map(int,input().split())
   maA=max(maA,a)
   AB.append((a,b))

dp=[inf]*(h+maA+1)
dp[0]=0
for i in range(h+1):
   for aj,bj in AB:
      dp[i+aj]=min(dp[i+aj],dp[i]+bj)
print(min(dp[h:]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    h, n = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(n)]

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

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

    print(dp[-1])
resolve()

Submission status: Accepted

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

def main():
    H,N = map(int,input().split())
    x = []
    ma = 0
    for _ in range(N):
        a,b = map(int,input().split())
        ma = max(ma,a)
        x.append((a,b))
    INF = 10**18
    
    dp = [INF for _ in range(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 x)
    
    print(min(dp[H:]))

if __name__ == "__main__":
    main()