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 itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


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


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


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    H, N = MI()
    A = [0] * N
    B = [0] * N
    dp = [IINF] * (H+1)
    dp[0] = 0

    for i in range(N):
        A[i], B[i] = MI()
        # AB[i] = (A / B, A, B)

    for i in range(N):
        dp_next = [IINF] * (H + 1)
        for j in range(H+1):
            dp_next[j] = min(dp[j], dp_next[j])
            if j + A[i] <= H:
                dp_next[j+A[i]] = min(dp_next[j+A[i]], dp_next[j] + B[i])
            else:
                # print(i, j, dp_next[j] + B[i], dp_next[j])
                dp_next[H] = min(dp_next[H], dp_next[j] + B[i])
                # print(dp_next[H])
        dp = dp_next
        # print(dp)

    print(dp[H])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

INF = float('inf')

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

dp[0][0] = 0

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

print(dp[N][H])

Submission status: Accepted

Solution code:
def DP():
  H,N,*T = map(int,open(0).read().split())
  
  #dpテーブルの設定と初期化
  dp = [0] + [10 ** 9] * H
  
  #各魔法について
  for d,c in zip(*[iter(T)] * 2):
    #d,cはそれぞれ魔法ダメージと魔法のコスト
    #dpテーブルの各HPについて
    for j in range(H + 1):
      k = j - d
      if k < 0:
        k = 0
      #ダメージjを与える時のコストについて、
      #魔法iを新たに使った場合と、既存の最小コストを比較し更新する
      l = dp[k] + c
      if l < dp[j]:
        dp[j] = l
      
  print(dp[-1])
  
DP()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

H, N = MAP()
AB = [()]
for i in range(N):
    a, b = MAP()
    AB.append((a, b))

dp = list2d(N+1, 20007, INF)
dp[0][0] = 0
for i in range(1, N+1):
    a, b = AB[i]
    for j in range(20007):
        dp[i][j] = min(dp[i][j], dp[i-1][j])
        if j-a >= 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j-a] + b)
            dp[i][j] = min(dp[i][j], dp[i][j-a] + b)
print(min(dp[N][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 i in range(N)])
A = AB[:, 0]
B = AB[:, 1]

# インデックスはライフ 値はそれを以下にする最小MP
dp = np.array([0]*(H+1))
# dp = np.array([0 for i in range(H+1)])

for i in range(1, H+1):
    dp[i] = min(dp[np.maximum(i - A, 0)] + B)

print(dp[-1])

Submission status: Accepted

Solution code:
H, N  = map(int, input().split())
fs = [] # damage/MP
for i in range(N):
    fs.append(map(int, input().split()))
INF = 10**10
M = 2*10**4+1
dp = [INF]*M
dp[0] = 0
for i,(a,b) in enumerate(fs):
    # update
    for j in range(H):
        # 何回でも使っていい⇛dp[i+1][j]+b
        dp[j+a] = min(dp[j+a], dp[j]+b) 
print(min(dp[H:]))

Submission status: Accepted

Solution code:
H, N  = map(int, input().split())
# hitpoint H
# waza N
As = [] # damage
Bs = [] # MP comsumptions
for i in range(N):
    a,b = map(int, input().split())
    As.append(a)
    Bs.append(b)

INF = 10**10
M = H + max(As) + 1
dp = [INF]*M
dp[0] = 0
for i,(a,b) in enumerate(zip(As,Bs)):
    # update
    for j in range(H):
        # 何回でも使っていい⇛dp[i+1][j]+b
        dp[j+a] = min(dp[j+a], dp[j]+b) 
print(min(dp[H:]))

Submission status: Accepted

Solution code:
H, N  = map(int, input().split())
# hitpoint H
# waza N
As = [] # damage
Bs = [] # MP comsumptions
for i in range(N):
    a,b = map(int, input().split())
    As.append(a)
    Bs.append(b)

INF = 10**10
M = 21000
dp = [INF]*M
dp[0] = 0
for i,(a,b) in enumerate(zip(As,Bs)):
    # update
    for j in range(H):
        # 何回でも使っていい⇛dp[i+1][j]+b
        dp[j+a] = min(dp[j+a], dp[j]+b) 
print(min(dp[H:]))

Submission status: Accepted

Solution code:
import numpy as np
 
H,N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

A = np.array(A)
B = np.array(B)
DP = np.zeros(H+1)

for i in range(1,H+1):
    DP[i] = np.amin(DP[np.maximum(i - A, 0)] + B)
    
print(int(DP[-1]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np


H, N = [int(str) for str in input().strip().split()]
AB = np.array([[int(str) for str in input().strip().split()] for _ in range(N)])

dp = np.zeros(H + 1)
for h in range(1, H + 1):
    dp[h] = min(AB[:, 1] + dp[np.maximum(0, h - AB[:, 0])]) 
print(int(dp[-1]))

Submission status: Accepted

Solution code:
import sys
from pprint import pprint
import math

h, n = map(int, sys.stdin.readline().strip().split(" "))

a, b = [], []
for _ in range(n):
    a_i, b_i = map(int, sys.stdin.readline().strip().split(" "))
    a.append(a_i)
    b.append(b_i)

a_max = max(a)
dp = [[10**12] * (h+a_max+1) for _ in range(n+1)]

# dp[i][0]はコスト0
for i in range(n+1):
    dp[i][0] = 0

# i個の魔法
for i in range(n):
    # hの体力
    for j in range(h+a_max+1):
        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:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    H,N = map(int,input().split())
    # AB = [list(map(int,input().split())) for _ in range(N)]
    A = []
    B = []
    for i in range(N):
        temp = list(map(int,input().split()))
        A.append(temp[0])
        B.append(temp[1])

    # A = np.array(A)
    # B = np.array(B)

    maxA = max(A)
    INF = 10 ** 4 + 1

    dp = [[INF for j in range(H+maxA+1)] for i in range(N)]
    dp[0][0] = 0
    for j in range(1,H+maxA+1):
        time = (j+A[0]-1)//A[0]
        dp[0][j] = B[0] * time

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

    res = min(dp[N-1][H:])
    print(res)





main()

Submission status: Accepted

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

A_max = 10 ** 4
INF = float('inf')

dp = [INF] * (H + A_max + 1)
dp[0] = 0
for i in range(H):
    if dp[i] == INF:
        continue
    for a, b in AB:
        if dp[i] + b < dp[i + a]:
            dp[i + a] = dp[i] + b
print(min(dp[H:]))

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
# 効率順にソート
# 効率が同じなら、小規模な魔法を優先
AB.sort(key=lambda 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:
            val = b + dp(h - a)
            if val < best:
                best = val
            else:
                # 更新されなかった場合は、以降の魔法で更新されることはない
                break
        return best


print(dp(H))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


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


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


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    H, N = MI()
    A = [0] * N
    B = [0] * N
    dp = [[IINF] * (H+2) for i in range(N+1)]
    dp[0][0] = 0

    for i in range(N):
        A[i], B[i] = MI()
        # AB[i] = (A / B, A, B)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def e_crested_ibis_vs_monster():
    H, N = [int(i) for i in input().split()]
    Damage, Cost = [], []
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        Damage.append(a)
        Cost.append(b)

    # dp[i][j]: 最初の i 種類の魔法でモンスターに j ダメージ与える場合の消費魔力の最小値
    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):
            # i 番目の魔法を使わない場合
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            # i 番目の魔法を使う場合
            dp[i + 1][min(j + Damage[i], H)] = min(dp[i + 1][min(j + Damage[i], H)],
                                                   dp[i + 1][j] + Cost[i])
    return dp[N][H]

print(e_crested_ibis_vs_monster())

Submission status: Accepted

Solution code:
H, N = [int(str) for str in input().strip().split()]
AB = [[int(str) for str in input().strip().split()] for _ in range(N)]

dp = [0]
for h in range(1, H + 1):
    a, b = min(AB, key=lambda i: i[1] + dp[max(0, h - i[0])])
    dp.append(b + dp[max(0, h - a)])    
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.read

H, N, *AB = map(int, read().split())

A = np.array(AB[::2], np.int64)
B = np.array(AB[1::2], np.int64)

INF = 10 ** 10
dp = np.full(H + 1, INF, np.int64)
dp[0] = 0

for i in range(1, H + 1):
    dp[i] = (dp[np.maximum(i - A, 0)] + B).min()

print(dp[-1])

'''
pypyなら346ms

import sys

read = sys.stdin.read

H, N, *AB = map(int, read().split())

INF = 10 ** 10
dp = [INF] * (H + 1)
r = INF
dp[0] = 0

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, H + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
    r = min(r, min(dp[-a:]) + b)

print(min(r, dp[-1]))
'''

Submission status: Accepted

Solution code:
H,N=map(int,input().split())
L=[]
m=0
for i in range(N):
    T=[0,0]
    T[0],T[1]=map(int,input().split())
    L.append(T)
    m=max(m,T[0])
L=sorted(L,reverse=True)
L.insert(0,[0,0])
m+=1
DP=[[10**10 for i in range(H+1+m)] for j in range(N+1)]
DP[0][0]=0

for i in range(1,N+1):
    t=0
    DP[i][0]=0
    for j in range(H+1):
        DP[i][j]=min(DP[i][j],DP[i-1][j])
        t=min(DP[i][j],DP[i-1][j])+L[i][1]
        DP[i][j+L[i][0]]=min(DP[i][j+L[i][0]],t)
    DP[i][H]=min(DP[i][H:-1])
print(min(DP[N][H:-1]))

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10**18

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

Submission status: Accepted

Solution code:
def main():
  def cal(k):
    for a,b in AB:
      tmp = k-a
      if tmp<0:
        tmp = 0
      new = dp[tmp]+b
      if new<dp[k]:
        dp[k]=new
  H,N = map(int,input().split())
  AB = [list(map(int,input().split())) for _ in range(N)]
  mi_a,mi_b = min(AB,key = lambda x:x[1])
  INF = float('inf')
  dp = [0]+[mi_b]*mi_a+[INF]*H
  for i in range(mi_a+1,H+1):
    cal(i)

  print(dp[H])
main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H, N, *ab = map(int, read().split())
    A = []
    B = []
    for a, b in zip(*[iter(ab)] * 2):
        A.append(a)
        B.append(b)

    A = np.array(A)
    B = np.array(B)
    
    dp = np.full((H+1), np.inf)
    dp[0] = 0


    for i in range(1,H+1):
        dp[i] = np.min(dp[np.maximum(i - A, 0)] + B)

    print(int(dp[H]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,n = [int(i) for i in input().split()]
 
l = sorted([[int(i) for i in input().split()] for _ in range(n)],key = lambda x: x[0])
 
inf = float('inf')
memo = [inf for _ in range(10**5)]
memo[0] = 0
for i in range(h+1):
    for x,y in l:
        memo[i+x] = min(memo[i+x],memo[i] + y)
print(min(memo[h:]))

Submission status: Accepted

Solution code:
h,n = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for _ in range(n)]
 
inf = float('inf')
memo = [inf for _ in range(h+1)]
memo[0] = 0
for i in range(h+1):
    for x,y in l:
        j = min(i+x, h)
        memo[j] = min(memo[j],memo[i] + y)
print(memo[-1])

Submission status: Accepted

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

H, N = map(int, input().split())

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

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

# dp[i][0]はコスト0
for i in range(N+1):
    dp[i][0] = 0

# i個の魔法
for i in range(N):
    # hの体力
    for h in range(H+1):
        # 最後に倒すとき
        if h == H:
            # 攻撃力がHを超える時
            if A[i] > H:
                dp[i+1][h] = min(dp[i][h], B[i])
            # 超えてない時
            else:
                m = min(dp[i+1][h-A[i]:h])
                dp[i+1][h] = min(dp[i][h], m + B[i])
        # 魔法の攻撃力が足らない
        elif h < A[i]:
            dp[i+1][h] = dp[i][h]
        # 通常時
        else:
            dp[i+1][h] = min(dp[i][h], dp[i+1][h-A[i]] + B[i])


print(dp[N][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 i in range(N)])
A = AB[:, 0]
B = AB[:, 1]

# インデックスはライフ 値はそれを以下にする最小MP
dp = np.array([0 for i in range(H+1)])

for i in range(1, H+1):
    dp[i] = np.min(dp[np.maximum(i - A, 0)] + B)

print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np

H, N = map(int, input().split())
AB = np.array([list(map(int, input().split())) for i in range(N)])
A = AB[:, 0]
B = AB[:, 1]

# インデックスはライフ 値はそれを以下にする最小MP
dp = np.array([0 for i in range(H+1)])

for i in range(1, H+1):
    dp[i] = min(dp[np.maximum(i - A, 0)] + B)

print(int(dp[-1]))

Submission status: Accepted

Solution code:
import numpy as np

H, N = map(int, input().split())
AB = np.array([list(map(int, input().split())) for i in range(N)])
A = AB[:, 0]
B = AB[:, 1]

# インデックスはライフ 値はそれを以下にする最小MP
# dp = np.array([0 for i in range(H+1)])
# dp = np.array([10**10 for i in range(H+1)])
dp = np.array([np.inf for i in range(H+1)])
dp[0] = 0

for i in range(1, H+1):
    dp[i] = min(dp[np.maximum(i-A, 0)] + B)

print(int(dp[-1]))

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
damage = []
mp = []
 
for i in range(N):
    a, b = map(int, input().split())
    damage.append(a)
    mp.append(b)
 
dp = [[0]+[float("inf")]*H for _ in range(N + 1)]

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

print(dp[N][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 i in range(N)])
A = AB[:, 0]
B = AB[:, 1]

# インデックスはライフ 値はそれを以下にする最小MP
dp = np.array([10**10 for i in range(H+1)], dtype=int)
# dp = np.array([np.inf for i in range(H+1)], dtype=int)
dp[0] = 0

for i in range(1, H+1):
    # print(np.maximum(i-A, 0))
    dp[i] = min(dp[np.maximum(i-A, 0)] + B)

print(dp[-1])

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
H,N=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
#AB=sorted(AB,key=lambda x:x[1])
A=H+10**4+1
dp=[10**9 for i in range(H+10**4+1)]
dp[0]=0
for a,b in AB:
    for i in range(1,A):
        if i>=a:
            dp[i]=min(dp[i-a]+b,dp[i])

print(min(dp[H:]))

Submission status: Accepted

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

if h == 1:
    print(min(b))
else:
    dp = [0]*h
    dp[0] = min(b)
    for i in range(2,h+1):
        c = [0]*n
        for j in range(n):
            if i > a[j]:
                c[j] = b[j] + dp[i-a[j]-1]
            else:
                c[j] = b[j]
        dp[i-1] = min(c)
    print(dp[h-1])

Submission status: Accepted

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

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

print(dp[h])

Submission status: Accepted

Solution code:
import numpy as np


H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
a, b = np.array(AB, dtype=np.int64).reshape(N, 2).T

d = np.zeros(H + 1, dtype=np.int64)

for hp in range(1, H + 1):
    c = d[np.maximum(hp - a, 0)] + b
    d[hp] = np.amin(c)

print(d[H])

Submission status: Accepted

Solution code:

#import numpy as np

H,N=map(int,input().split())
weights=[list(map(int,input().split())) for _ in range(N)]
INF=100100101
#print(weight)
#print(value)

#print(weights)
dp=[INF]*(H+1)
for i in range(H+1):
    if i==0:
        dp[i]=0
    else:
        for j in weights:
            a=j[0]
            b=j[1]
            piv=max(0,i-a)  #use i-a's dp[] value as a pivot (if not exits(i-a<0), return dp[0])
            dp[i]=min(dp[i],dp[piv]+b) #the part which forcely treated as piv=0, returns min([weights]), other is treated as normal dp
    #print(dp)

print(dp[H])

Submission status: Accepted

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

INF = 10**10

dp = [INF for i in range(H+1)]
dp[0] = 0

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

Submission status: Accepted

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

INF = 10**10

dp = [INF for i in range(H+1)]
dp[0] = 0

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def dc(n, m):
    return -(-n // m)

# @mt
def slv(H, N, AB):

    dp = [INF] * (H+1)
    dp[0] = 0
    for a, b in AB:
        for h, bb in enumerate(dp):
            if bb == INF:
                continue
            n = min(H, h+a)
            dp[n]  = min(dp[n], bb+b)
    return dp[-1]


def main():
    H, N = read_int_n()
    AB = [read_int_n() for _ in range(N)]
    print(slv(H, N, AB))
    # H = 10**4
    # N = 10
    # AB = [[random.randint(1, 100), random.randint(1, 100)] for _ in range(N)]
    # print(slv(H, N, AB))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

INF = 10**10
#print(magic)

dp = [INF for i in range(H+1)]
dp[0] = 0

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

Submission status: Accepted

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

INF = 10**10
#print(magic)

AM = 0
for i in range(N):
    AM = max(AM,magic[i][0])
#print(AM)


dp = [INF for i in range(H+AM+1)]
dp[0] = 0

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

Submission status: Accepted

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

INF = 10**10
#print(magic)

AM = 0
for i in range(N):
    AM = max(AM,magic[i][0])
#print(AM)


dp = [INF for i in range(H+AM+1)]
dp[0] = 0

for i in range(1,H+AM+1):
    for j in range(N):
        if magic[j][0] > i:
            dp[i] = min(dp[i],magic[j][1])
        else:
            dp[i] = min(dp[i-magic[j][0]]+magic[j][1],dp[i])
ans = INF
print(dp[H])

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
inf =1000100001001000
dp = [inf for _ in range(H+1)]
 
# min_cost = np.inf
dp[0]=0
for n in range(N):
    a,b =  map(int, input().split())
    for h in range(H):
        nj = min(h+a,H)
        dp[nj] = min([dp[nj],dp[h]+b])
        
print(int(dp[H]))

Submission status: Accepted

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

eff = 0
eff_index = 0
for i in range(n):
    a[i], b[i] = [int(_) for _ in input().split()]

max_a = max(a)

ans = float('inf')
H = h + max_a
dp = [float('inf')] * (H+1)
# dp[i] iのダメージを与える最小消費魔力
dp[0] = 0
for i in range(H+1):
    for j in range(n):
        if i >= a[j]:
            dp[i] = min(dp[i], dp[i-a[j]]+b[j])

    if i >= h:
        ans = min(ans, dp[i])
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

H, N = map(int, input().split())

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

INF = 10 ** 10
dp = [INF] * 20000
dp[0] = 0

for i in range(N):
    for h in range(H):
        a, b = MAGIC[i]

        if dp[h+a] > (dp[h] + b):
            dp[h+a] = dp[h] + b

print(min(dp[H:]))

Submission status: Accepted

Solution code:
def main():
    H,N = map(int, input().split())
    A = [None]*N
    B = [None]*N
    for i in range(N):
        A[i], B[i] = map(int, input().split())
    
    dp = [float("inf")] * (H+1)
    dp[0] = 0

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

    print(dp[H])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def calc_m_value(M, A, B, N, h):
    return min([M[h - A[i]]+B[i] if A[i] <= h else B[i] for i in range(N)])
 
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)
 
M = [0] * (H+1)
for i in range(1, H+1):
    M[i] = calc_m_value(M, A, B, N, i)
 
print(M[H])

Submission status: Accepted

Solution code:
INF = 1145141919810893

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]=体力がちょうどiのモンスターを倒すのに必要な魔力の最小値
#もしそのような魔力が存在しない場合、INF
#INFは10^9くらいあれば足りると思う(適当)
dp = [INF]*20000
dp[0]=0
#体力が0のモンスターを倒すのに必要な魔力は0
#iは小さい順に決定することができる
#なぜなら、i<jのとき決定したdp[j]の値はdp[i]に影響しないから
for i in range(H):
    #dp[H]から配る遷移は、必ずdp[H]より大きい値を配ることになるので、不要
    #よってH-1までやればOK
    #dp[i]の値はこの時点で確定する
    if dp[i]==INF:
        continue
    for j in range(N):
        #いわゆる配るDP
        dp[i+A[j]]=min(dp[i+A[j]],dp[i]+B[j])

#これで答えはdp[H]であるかというと、そうとは限らない
#なぜなら、dp[H+1]に行くコストがdp[H]に行くコストより安いかもしれないから
#今回は「与えるダメージがH以上」で条件を達成することができる
#なので、H以上のdpについて精査して、最もコストが低いものが答えである
Ans=INF
for d in dp[H:]:
    Ans=min(Ans,d)
print(Ans)

Submission status: Accepted

Solution code:
import bisect
H,N = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[10**18]*(H+1) for _ in range(N+1)]
dp[0][0]=0
mi=10**9
for i in range(N):
  for w in range(H+1):
    dp[i+1][w]=min(dp[i+1][w],dp[i][w])
    dp[i+1][min(w+AB[i][0],H)]=min(dp[i+1][min(w+AB[i][0],H)],dp[i+1][w]+AB[i][1])
print(dp[N][H])

Submission status: Accepted

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

# dp[i][h] := i-1 番目の魔法の中から，減らす体力が h を達成するように選んだ時の魔法の最小値
# DP テーブル
max_h = H + max(A)
dp = [[float("inf")] * (H + 1) for _ in range(N+1)]
dp[0][0] = 0

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

Submission status: Accepted

Solution code:
import math

def resolve():
    import sys
    input = sys.stdin.readline
    
    H, N = map(int, input().split())
    v = []
    w = []
    for i in range(N):
        a, b = map(int, input().split())
        v.append(a)
        w.append(b)

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

    # initiate
    for i in range(H):
        dp[0][i] = w[0] * (math.ceil((i + 1) / v[0])) # 魔法1だけでHまで削るのに必要なコスト(MP)

    for i in range(1, N):
        for j in range(H):
            if j+1 < v[i]: 
                # 敵のHPが魔法iで与えるダメージより小さい場合、そのままの組み合わせか新しい魔法1回とで、コストの少ない方を選ぶ
                dp[i][j] = min(dp[i-1][j], w[i])
            else:
                # 大きい場合、そのままの組み合わせと、魔法iを取り込んだ組み合わせで、コストの少ない方を選ぶ
                dp[i][j] = min(dp[i-1][j], dp[i][j - v[i]] + w[i])

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
INF = 10**12

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

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
l={}
ans=0
for i in range(n):
    a,b=map(int,input().split())
    if a in l:
        l[a]=min(l[a],b)
    else:
        l[a]=b
d=[0]*10005
for i in range(h):
    for j in l:
        a,b=j,l[j]
        x=d[i]+b
        y=min(10004,i+a)
        if i==0 or (d[i]!=0 and d[y]==0):
            if d[y]==0:
                d[y]=x
            else:
                d[y]=min(d[y],x)
        elif d[i]!=0 and d[y]!=0:
            d[y]=min(d[y],x)

for i in range(h,10005):
    if ans==0:
        ans=d[i]
    elif d[i]!=0:
        ans=min(ans,d[i])
print(ans)