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:
# 個数制限なしナップザック問題
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]
# i番目までの魔法を使った時にjを削るために必要な最小のコスト
dp = [[10**10]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H+1):
        # 使わない場合
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # 使う場合
        dp[i+1][min(j+magic[i][0], H)] = min(dp[i+1][min(j+magic[i][0], H)], dp[i+1][j] + magic[i][1])
print(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)

# 個数制限なしナップサック
# i番目までの魔法を使ったときにHダメージを実現できるときの最小の魔力
dp = [[10**10]*(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(H, j+A[i])] = min(dp[i][j]+B[i], dp[i+1][j]+B[i], dp[i+1][min(j+A[i], H)])

print(dp[N][H])

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
dp=[10**9]*(h+1)
dp[0]=0
for i in range(n):
    a,b=map(int,input().split())
    for j in range(h):
        k=min(j+a,h)
        dp[k]=min(dp[k],dp[j]+b)
print(dp[h])

Submission status: Accepted

Solution code:
H, N, *AB = map(int, open(0).read().split())

dp = [0] * (H + max(AB[::2]))

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

print(min(dp[H:]))

Submission status: Accepted

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

DP = [0 for i in range(10**4+1)] #DP[h]=体力hのやつを倒す最小mp
#DPのrangeを大きくとることで後々計算が簡単になる

for h in range(1,H+1):
    DP[h] = min((DP[h - a] + b) for a,b in AB )
    #注：h - a < 0の場合もある.
    #　　この場合 -(h - a) >= len(DP) のときにout of rangeになる
    #これを防ぐにはlen(DP)を十分大きくしておけばいい
    #h - a < 0 のときはDP[h-a] = 0に初期化しておくとbだけが消費mpになる

print(DP[H])

Submission status: Accepted

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

dp[0] = 0

for i in range(N):
  a, b = map(int, input().split())
  
  for j in range(H):
    dp[min(j+a, H)] = min(dp[min(j+a, H)], dp[j] + b)


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

DP = [0 for i in range(H+1)] #DP[h]=体力hのやつを倒す最小mp

min_mp = 10**9
for i in range(N):
    if min_mp > AB[i][1]:
        min_mp = AB[i][1]
        min_mp_i = i

for h in range(1,min(AB[min_mp_i][0],H)+1):
    #最小消費mpの技でオーバーキルの場合にDP[h]がout of rangeになる
    DP[h] = min_mp

for h in range(AB[min_mp_i][0]+1,H+1):
    DP[h] = min((DP[h - a] + b) for a,b in AB )
    #最小消費mpの技で初期化しないとh - a >= 0を満たすaの存在が怪しい

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 = [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:
inf = 10 ** 18
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 = [inf] * (h + max_a)
dp[0] = 0
for i in range(1, h + max_a):
    dp[i] = min(dp[i-a] + b for a, b in ab)
print(min(dp[h:]))

Submission status: Accepted

Solution code:
# coding=utf-8
# Date: 2020-01-08
# Author: lee215
get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: list(map(int, raw_input().strip().split()))
getss = lambda n: [gets() for _ in range(n)]


H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur // a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in range(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print(min(dp[H:]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    hmax = H + max(A)
    cost = [0] * hmax
    magics = [(a, b) for a, b in zip(A,B)]
    for i in range(1, hmax):
        for a, b in magics:
            if i >= a:
                cost[i] = min(cost[i-a]+b, cost[i]) if cost[i] > 0 else cost[i-a]+b
            else:
                cost[i] = min(b, cost[i]) if cost[i] > 0 else b
    #print(cost)
    print(min(cost[H:]))

def solve_dijkstra(H: int, N: int, A: "List[int]", B: "List[int]"):
    nodes = {0: 0}
    fixed = 0
    unfixed = set()
    while True:
        cost = nodes[fixed]
        for a, b in zip(A,B):
            new_node = fixed + a
            last = nodes.get(new_node, 999999999)
            new_cost = cost + b
            if last > new_cost:
                nodes[new_node] = new_cost
                unfixed.add(new_node)
        fixed = min(unfixed)
        if fixed >= H:
            break
        unfixed.remove(fixed)
    print(min([v for k, v in nodes.items() if k >= H]))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    mxA = 10 ** 4
    dp = [[10**15 for i in range(h+1+mxA)] for i in range(n+1)]

    for i in range(n+1):
        dp[i][0] = 0

    for i in range(n):
        for sum_dam in range(h+1+mxA):
            if sum_dam-l[i][0]>=0:
                dp[i+1][sum_dam] = min(dp[i+1][sum_dam],  \
                                dp[i][sum_dam - l[i][0]] + l[i][1],  \
                                dp[i+1][sum_dam-l[i][0]] + l[i][1])
            dp[i+1][sum_dam] = min(dp[i+1][sum_dam], dp[i][sum_dam])

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
mahou=[list(map(int,input().split())) for i in range(n)]
INF=10**10
dp=[INF]*(h+1)#そのHPを与えるのに必要な最小MP
dp[0]=0
for hp in range(h+1):
  for use in mahou:
    dp[hp]=min(dp[max(0,hp-use[0])]+use[1],dp[hp])
print(dp[h])

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, floor
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()
temp = [LIST() for _ in range(N)]
temp = [list(x) for x in zip(*temp)]
A, B = temp[0], temp[1]

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

for i in range(N):
	for j in range(H + a + 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:H + max(A) + 1]))

Submission status: Accepted

Solution code:
def solve():
    H,N = map(int, input().split())
    # Aが消費HP, Bが消費MP
    ABs = [list(map(int, input().split())) for _ in range(N)]
    # dp_table = [[10**9]*(H+1)]+[[0]*(H+1) for _ in range(N)]
    dp_table = [[0]*(H+1) for _ in range(N+1)]
    # dp_table[i][j] : i番目の魔法から消化HPがj以上となる、MPの最小値
    for j in range(1,H+1): dp_table[0][j] = 10**9
    # print(dp_table)
    for i in range(N):
        for j in range(H+1):
            if j-ABs[i][0]<0:
                dp_table[i+1][j] = min(dp_table[i][j], ABs[i][1])
            else:
                dp_table[i+1][j] = min(dp_table[i][j], dp_table[i+1][j-ABs[i][0]]+ABs[i][1])
                
    print(dp_table[N][H])
    
solve()

Submission status: Accepted

Solution code:
def main():
    INF = 10**9
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(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:]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(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:]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    dp[0] = 0
    for i in range(H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np 

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

A,B = np.array([list(map(int,input().split())) for i in range(N)]).T

dp = np.zeros(H+1,dtype=np.int32)

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

Submission status: Accepted

Solution code:
import numpy as np 

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)

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

dp = np.zeros(H+1,dtype=np.int32)

for i in range(1,H+1):
    dp[i] = np.amin(dp[np.maximum(i-A,0)]+B)
    
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)]

M = max(a for a,b in AB)

dp = [0]*(H+M)

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

Submission status: Accepted

Solution code:
from sys import stdin


## This code doesn't pass the test
# def get_result(data):
#     H, N = data[0]
#     A_and_B = np.array(data[1:])
#     calc_efficient = np.array(list(map(lambda x: float(x[0] / x[1]), A_and_B)))
#     sorted_index = np.argsort(-calc_efficient)

#     cost = 0
#     remainder_H = H
#     for i in sorted_index:
#         A, B = A_and_B[i]
#         quotient = remainder_H // A
#         if quotient > 0:
#             cost += B * quotient
#             remainder_H = remainder_H - A * quotient
#         else:
#             if remainder_H > 0:
#                 continue
#             else:
#                 break

#     return cost

## 答え (DP, ナップザック問題の典型らしい) (pythonだとTLEになる)
# 自分の解法は典型的なハマり方をしたっぽい

def get_result(data):
    # 初期化
    H, N = data[0]
    A_and_B = data[1:]
    A = [0 for _ in range(N)]
    B = [0 for _ in range(N)]
    for i in range(N):
        Ai, Bi = A_and_B[i]
        A[i] = Ai
        B[i] = Bi

    # 最小化問題だから無限で初期化
    # DP[j] = Aの和が j の時の最小コスト (魔力)
    # 計算量は、O(NH)なのでHが少なくなるようにテーブルは作る
    inf = float("inf")
    # N × H (制約条件) のテーブルを作成
    dp =[inf for _ in range(H+1)]
    # 初期値
    dp[0] = 0

    # DP (コードはなんとなく理解できた)
    for i in range(H):
        for j in range(N):
            # 魔力1つずつについてloopさせる
            if (i+1) - A[j] < 0:
                dp[i+1] = min(dp[i+1], dp[0] + B[j])
            else:
                dp[i+1] = min(dp[i+1], dp[i+1-A[j]] + B[j])

    return dp[H]

if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

Submission status: Accepted

Solution code:
"""
前処理
"""
import numpy as np
H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    ai, bi = map(int, input().split())
    """
    入力したものをそれぞれリストに格納していく、これは真似ていこう
    """
    A.append(ai)
    B.append(bi)

"""
配列に変換
"""
A = np.array(A)
B = np.array(B)

"""
処理
"""
#0からHまで
dp = np.zeros(H+1, dtype=np.int64)
dp[0] = 0

for i in range(1, H+1):
    # モンスターのHPがiである場合...
    # dp[i] ... モンスターのHPがiである時の，最小魔力合計
    dp[i] = np.amin(dp[np.maximum(i-A, 0)] + B)

"""
output
"""
print(dp[H])

Submission status: Accepted

Solution code:
# coding: utf-8
H,N=map(int,input().split())
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))
 
INF=10**9

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

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

print(dp[H])

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
dp = [1 << 31] * (h + 10**4)
dp[0] = 0
for i in range(h):
    for a, b in AB:
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))

Submission status: Accepted

Solution code:
# coding: utf-8
H, N = map(int, input().split())
L = []
for i in range(N):
    L.append(list(map(int, input().split())))
dp = [float("inf") for _ in range(H+1)] 
dp[0] = 0
top = 10**9
for i in range(1, H+1):
    for j in range(N):
        a, b = L[j]
        if i <= a:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i-a] + b)
    # print(*dp)
print(dp[H])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
 
h,n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]

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

for a,b in AB:
    for i in range(h):
        if dp[i]!=float("inf"):
            dp[min(i+a,h)]=min(dp[min(i+a,h)],dp[i]+b)
print(dp[-1])

Submission status: Accepted

Solution code:
# coding: utf-8
H,N=map(int,input().split())
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))

INF=10**9

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

for i in range(N+1):
    dp[i][0]=0


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


print(dp[N][H])

Submission status: Accepted

Solution code:
def chmin(a, b):
  if (a > b):
    return b

  return a

def chmax(a, b):
  if (a < b):
    return b

  return a

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

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

for n in range(N):
  for h in range(0, H+1):
    dp[n+1][h] = chmin(dp[n+1][h], dp[n][h])
    dp[n+1][min(h+li[n][0], H)] = chmin(dp[n+1][min(h+li[n][0], H)], dp[n+1][h]+li[n][1])

print(dp[N][H])

Submission status: Accepted

Solution code:
"""
前処理
"""
import numpy as np
H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    ai, bi = map(int, input().split())
    """
    入力したものをそれぞれリストに格納していく、これは真似ていこう
    """
    A.append(ai)
    B.append(bi)

"""
配列に変換
"""
A = np.array(A)
B = np.array(B)

"""
処理
"""
#0からHまで
dp = np.zeros(H+1, dtype=np.int64) 
dp[0] = 0

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

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

# 最強の魔法の特定
a_max = max(a for a, b in ab)
# 動的計画法用の配列の定義及び初期化
dp = [0]*(h + a_max)

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

print(min(dp[h:]))

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
s=[list(map(int, input().split())) for i in range(m)]
x=max(a for a,b in s)
dp=[0]*(n+x)
for i in range(0,n+x):
  if i>0:
    dp[i]=min(dp[i-a]+b for a,b in s)
print(min(dp[n:]))

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

H,N = imn()
AB = [iln() for _ in range(N)]
MAX_H = 10**4+1
dp = [10**10 for _ in range(MAX_H)]
dp[0] = 0

for i in range(N):
    for j in range(MAX_H):
        if j - AB[i][0] >= 0:
            dp[j] = min(dp[j], dp[j-AB[i][0]]+AB[i][1])
ans = 10 ** 10
for i in range(H, MAX_H):
    ans = min(ans, dp[i])
print(ans)

Submission status: Accepted

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


def main():
    h, n = map(int, input().split())
    a = [0 for _ in range(n)]
    b = [0 for _ in range(n)]
    inf = float('inf')
    dp = [inf for _ in range(2 * 10 ** 4 + 100)]
    dp[0] = 0

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

    for i in range(h):
        for j, ai in enumerate(a):
            if dp[i] == inf:
                continue

            dp[i + ai] = min(dp[i + ai], dp[i] + b[j])

    print(min(dp[h:]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# 最強の魔法の特定
a_max = max(a for a, b in ab)
# 動的計画法用の配列の定義及び初期化
dp = [0]*(h + a_max)

for i in range(h + a_max):
	if i > 0:
		dp[i] = min(dp[i - a] + b for a, b in ab)

print(min(dp[h:]))

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
s=[list(map(int, input().split())) for i in range(m)]
x=max(a for a,b in s)
dp=[0]*(n+x)
for i in range(0,n+x):
  if i>0:
    dp[i]=min(dp[i-a]+b for a,b in s)
print(min(dp[n:]))

Submission status: Accepted

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

from math import floor
import numpy

def main():
  h, n = map(int, input().strip().split())
  As, Bs = numpy.array([list(map(int, input().strip().split())) for _ in range(n)]).T

  dp = numpy.zeros(h+1)
  for i in range(1, len(dp)):
    dp[i] = numpy.min(dp[numpy.maximum(i - As, 0)] +  Bs)
  print(int(dp[-1]))



if __name__=='__main__':
  main()

Submission status: Accepted

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

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)

Ama = max(A)

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

for i in range(h+1):
    for j in range(n):
        dp[i+A[j]]=min(dp[i+A[j]],dp[i]+B[j])
print(min(dp[h:]))

Submission status: Accepted

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

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)

Ama = max(A)

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

for i in range(n):
    for j in range(A[i],h+Ama+1):
        dp[j]=min(dp[j],dp[j-A[i]]+B[i])

print(min(dp[h:]))

Submission status: Accepted

Solution code:
import numpy as np

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

A = []
B = []
for i 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.full((H+1), np.inf)
dp[0] = 0

def solve():
	for i in range(1, H + 1):
		dp[i] = np.amin(dp[np.maximum(i - A, 0)] + B)
	return int(dp[H])

print(solve())

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 + 10010)
dp[0] = 0

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

Submission status: Accepted

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

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)

Ama = max(A)

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

for i in range(n):
    for j in range(A[i], h+Ama+1):
        dp[j]=min(dp[j],dp[j-A[i]]+B[i])
print(min(dp[h:]))

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, n = list(map(int, input().rstrip('\n').split()))
    ab = []
    ma = 0
    for i in range(n):
        a, b = list(map(int, input().rstrip('\n').split()))
        ab.append([a, b])
        ma = max(ma, a)
    ls = [10 ** 10] * (h + 1 + ma)
    ls[0] = 0
    for i in range(n):
        for j in range(h):
            ls[j+ab[i][0]] = min(ls[j] + ab[i][1], ls[j+ab[i][0]])
    print(min(ls[h:]))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
H,N = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(N)]
dp = [float('inf') for i in range(H+1)]
dp[0] = 0
for i in range(N):
    a,b = AB[i]
    for j in range(H+1):
        if j+a > H:
            dp[H] = min(dp[H],dp[j]+b)
        else:
            dp[j+a] = min(dp[j+a],dp[j]+b)
print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np

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

A = []
B = []
for i 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.full((H+1), np.inf)
dp[0] = 0

def solve():
    for i in range(1, H + 1):
        dp[i] = np.amin(dp[np.maximum(i - A , 0)] + B)
    return int(dp[H])

print(solve())

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
s=[list(map(int, input().split())) for i in range(m)]
x=max(a for a,b in s)
dp=[0]*(n+x)
for i in range(0,n+x):
  if i>0:
    dp[i]=min(dp[i-a]+b for a,b in s)
print(min(dp[n:]))

Submission status: Accepted

Solution code:
import numpy as np

n,m=map(int,input().split())
a=np.zeros(m,dtype=int)
b=np.zeros(m,dtype=int)
for i in range(m):
    a[i],b[i]=map(int,input().split())
dp=np.zeros(10001,dtype=int)
for i in range(1,10001):
    dp[i]=(dp[i-a]+b).min()
print(dp[n])

Submission status: Accepted

Solution code:
import numpy as np

h, n = map(int,input().split())
a = np.zeros(n, dtype = int)
b = np.zeros(n, dtype = int)
for i in range(n):
    a[i], b[i] = map(int,input().split())

dp = np.zeros(10001, dtype = int)

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

print(dp[h])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
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:
# ダイナミック・プログラミング
# PythonではTLEを起こしてしまう例

INF = float('inf')

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

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

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
dp[0][0] = 0 # 初期化処理
for i in range(0,N):
    for j in range(0,H+1):
        a, b = j+A[i], H
        min_h = a
        if a>b:
            min_h = b
        a, b = dp[i+1][j], dp[i][j]
        if a>b:
            dp[i+1][j] = b
        a, b = dp[i+1][min_h], dp[i+1][j]+B[i]
        if a>b:
            dp[i+1][min_h] = b

print(dp[N][H])

Submission status: Accepted

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

Submission status: Accepted

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

inf = 10**8
dp = [[inf for i in range(h+10001)] for j in range(n+1)]
dp[0][0] = 0
a = []
b = []
for i in range(n):
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)
#dp[i][j]: i番目の魔法まででjダメージ与えるときの最小魔力
for i in range(n):
    for j in range(h+10001):
        if j-a[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j-a[i]] + b[i], dp[i+1][j])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = min(dp[n][h:])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
h,n=map(int,input().split())    
ab=np.array([tuple(map(int,input().split())) for _ in range(n)])
dp=np.zeros(h+1,dtype="int")
for i in range(1,h+1):
    dp[i]=np.min(dp[np.maximum(i-ab[:, 0],0)]+ab[:,1])
print(dp[-1])

Submission status: Accepted

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

"""

9 3
8 3
4 2
2 1
ans 4

7 2
4 4
2 3
ans 8

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

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
ans 139815
"""; test = """
"""
import builtins
test = list(reversed(test.strip().splitlines()))
input = test.pop if test else builtins.input


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


dp = np.zeros(h + 1, dtype="int")
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i - ab[:, 0], 0)] + ab[:, 1])
    ### dp[i] = min(dp[max(i-c[0], 0)] + c[1] for c in ab) ###
print(dp[-1])

Submission status: Accepted

Solution code:
h, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(k)]
maxa = max(a for a,b in ab)
dp = [0 for i in range(h+maxa)]
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 sys
input = sys.stdin.readline


def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def main():
    H, N = map(int, input().split())
    magics = tuple(readlines(N))
    INF = 10**9
    dp = [INF]*(H+10**4+1)
    dp[0] = 0
    for a, b in magics:
        for i in range(H):
            if dp[i] != INF:
                t = dp[i] + b
                if t < dp[i+a]:
                    dp[i+a] = t
    print(min(dp[H:]))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

for i in range(h):
    for a, b in l:
        x=i+a
        if x>h:
            x=h
        y=dp[i]+b
        if y<dp[x]:
            dp[x]=y

print(dp[h])

Submission status: Accepted

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

# dp[i][j] = 魔法iまでからダメージの総和がj以上になるように選んだ時の魔力の最小値
# dp[i][j] = min(dp[i][j - a] + b, dp[i - 1][j])

dp = [[float('inf')] * (H + 1)] * (N + 1)
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    a, b = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i][max(0, j - a)] + b, dp[i - 1][j])
print(dp[N][H])

Submission status: Accepted

Solution code:
import numpy as np

H,N = map(int,input().split())
S=[None for i in range(N)]
for i in range(N):
  S[i] = list(map(int,input().split()))
S = np.array(S)

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

print(int(dp[-1]))

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
a, b = zip(*(list(map(int, input().split())) for _ in range(N)))
maxA = max(a)
 
inf = float("inf")
dp = [inf] * (H+maxA+1)
dp[0] = 0
 
for j in range(N):
    for i in range(a[j], H+maxA+1):
        dp[i] = min(dp[i], dp[i-a[j]]+b[j])
 
print(min(dp[H:]))

Submission status: Accepted

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

maxa = max(a)
hmaxa = h+maxa
dp = [0 for _ in range(hmaxa)]

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

print(min(dp[h:]))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
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 i in range(1, H + max_damage):
    dp[i] = min(dp[i - damage] + cost for damage, cost in magic)

ans = min(dp[H:])

print(ans)