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 sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, N = lr()
U = 20000 # max(H)+max(A) これ以上は関係ない
INF = 10 ** 8
dp = np.full(U, INF, np.int64)
dp[0] = 0
for i in range(N):
    a, b = lr()
    n = (U + (-U)%a)
    #列のサイズはa
    dp = np.resize(dp, n).reshape(-1, a)
    dp -= (np.arange(n//a) * b)[:, None]
    dp = np.minimum.accumulate(dp, axis=0)
    dp += (np.arange(n//a) * b)[:, None]
    dp = np.ravel(dp)[:U]

print(min(dp[H:]))
#34

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:

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())
"""
# i番目までの魔法を使い, モンスターの体力をj以上減らすのに必要な魔力の最小値(個数制限なしナップザック)
dp = [[float("inf")]*(H+1) for _ in range(N+1)]
dp[0][0] = 0

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

print(dp[N][H])
"""
# メモリ削減(ただし, 計算時間は増えてしまう)
# 配るDPで考える
# モンスターの体力をj減らすのに必要な魔力の最小値
dp = [float("inf")]*(H+10**4)
dp[0] = 0
for i in range(N):
    for j in range(H):
        dp[j+A[i]] = min(dp[j+A[i]], dp[j]+B[i])

ans = float("inf")
for j in range(H, H+10**4):
    ans = min(ans, dp[j])

print(ans)

Submission status: Accepted

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

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

#i番目までの魔法を使い, モンスターの体力をj以上減らすのに必要な魔力の最小値(個数制限なしナップザック)
dp = [[float("inf")]*(H+1) for _ in range(N+1)]
dp[0][0] = 0

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

print(dp[N][H])

Submission status: Accepted

Solution code:
h, n = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(n)]
max_a = max(a for a, _ in lst )
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 lst)
print(min(dp[h:]))

Submission status: Accepted

Solution code:
import math

DP_MAX = 2*10**4 + 1
INF = 2*10**8

H,N = map(int,input().split())
M = [0]*N
for _ in range(N):
    M[_] = tuple(map(int,input().split()))

DP = [0]+[INF]*(DP_MAX - 1)

for A,B in M:
    for j in range(1,DP_MAX):
        if j - A >= 0:
            DP[j] = min(DP[j],DP[j - A]+B)

print(min(DP[H:]))

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    h,n = map(int,input().split())
    ab = [list(map(int,input().split())) for i in range(n)]
    a = [ab[i][0] for i in range(n)]
    b = [ab[i][1] for i in range(n)]
    inf = float("inf")
    dp = [inf for i in range(h+max(a)+1)] #dp[i]...体力をi削るために必要な最低の魔力
    dp[0] = 0
    for i in range(n):
        for j in range(h+1):
            dp[j+a[i]] = min(dp[j]+b[i],dp[j+a[i]])

    print(min(dp[h:]))
if __name__ == "__main__":
    main()
#endline===============================================

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())
ma = max(A)
dp = [float("inf")] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))

Submission status: Accepted

Solution code:
import numpy as np
h, n = map(int, input().split())
a = [0 for i in range(10**4+1)]
b = [i for i in range(10**4+1)]
used = [False for i in range(10**4+1)]
for i in range(n):
    t = [int(i) for i in input().split(" ")] 
    if used[t[1]] == True:
        a[t[1]-1] = min(a[t[1]-1], t[0])
    else:
        a[t[1]] = t[0]
        used[t[1]] = True
a = np.array(a)[np.array(used)]
b = np.array(b)[np.array(used)]

dp = np.array([0 for i in range(h+1)])
for i in range(1, h+1):
    temp = i-a
    temp[temp<0] = 0
    dp[i] = np.min(dp[temp] + b)
print(dp[-1])

Submission status: Accepted

Solution code:
import math
#import numpy as np
#"""
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))


#"""
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
dp[0][0]=0
ma=list(map(int,input().split()))
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0])*ma[1]
#print(np.array(ma))
for i in range(1,n):
    ma=list(map(int,input().split()))
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(h+1):
        if j<ma[0]:
            cal=ma[1]
        else:
            #print("sansyo before")
            cal=ma[1]+dp[i][j-ma[0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


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

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:
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 = [[10**10] * (H + 1) for _ in range(N+1)]

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

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

Submission status: Accepted

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

Submission status: Accepted

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

skill_list = []
for i in range(N):
  skill_list.append(list(map(int, input().split())))

max_B = 0
for i in range(N):
  if skill_list[i][0] > max_B: max_B = skill_list[i][0]

dp = [float('inf') for i in range(H + max_B)]

dp[0] = 0
for i in range(H):
  for j in range(N):
    if dp[i + skill_list[j][0]] > dp[i] + skill_list[j][1]:
      dp[i + skill_list[j][0]] = dp[i] + skill_list[j][1]

print(min(dp[H : H + max_B]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15


def main():
    h, k = getlist()
    mag = []
    for i in range(k):
        mag.append((getlist()))
    dp = [INF for i in range(h+1)]
    dp[0] = 0
    for i in range(h):
        cur = dp[i]
        for ma in mag:
            a, b = ma
            if i + a >= h:
                tgt = h
            else:
                tgt = i + a
            if dp[tgt] > cur + b:
                dp[tgt] = cur + b
    print(dp[-1])
    # mag.sort()


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Accepted

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

dp=[inf]*(h+maA+1)
dp[0]=0
for i in range(h):
   for a,b in L:
       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())
inf = 10**10
dp = [[inf for i in range(h+1)] for j in range(n+1)]
#dp[i][j] := i番目の魔法まで考えたとき、hpをh減らす最小コスト
dp[0][0] = 0
for i in range(1,n+1):
    damage, cost = map(int, input().split())
    for j in range(h+1):
        if j - damage < 0:
            dp[i][j] = min(cost, dp[i][j], dp[i-1][j])
        else:
            dp[i][j] = min(dp[i][j - damage] + cost, dp[i-1][j])
print(dp[-1][h])

Submission status: Accepted

Solution code:
def main():
  
  h,n=map(int,input().split())
  AB=tuple([list(map(int,input().split()))for _ in range(n)])
  
  DP=[float("inf") for _ in range(h+2)]
  DP[0]=0
  for i in range(1,h+2):
    for a,b in AB:
      if i<=a:
        DP[i]=min(DP[i],b)
      else:
        DP[i]=min(DP[i],DP[i-a]+b)
        
  print(DP[h])
  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
x=input().split()
h=int(x[0])
n=int(x[1])
import numpy as np
a=np.full(n,0,int)
b=np.full(n,0,int)
for k in range(n):
  x=input().split()
  a[k]=int(x[0])
  b[k]=int(x[1])
m=max(a)  
inf=10**8
dp=np.full(h+m+1,inf,int)
dp[0]=0
for k in range(1,h+m):
  dp[k]=(dp[k-a]+b).min()
print(dp[h:h+m].min())

Submission status: Accepted

Solution code:
x=input().split()
h=int(x[0])
n=int(x[1])
import numpy as np
a=np.full(n,0,int)
b=np.full(n,0,int)
for k in range(n):
  x=input().split()
  a[k]=int(x[0])
  b[k]=int(x[1])
m=max(a)  
inf=10**8
dp=np.full(h+m,inf,int)
dp[0]=0
for k in range(1,h+m):
  dp[k]=(dp[k-a]+b).min()
print(dp[h:h+m].min())

Submission status: Accepted

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

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


#
# MAX_NUM=9999999999
# ab=[]
# for _ in range(n):
#     ab.append(list(map(int,input().split())))
# dp=[MAX_NUM for _ in range(h+1)]
# dp[0]=0
#
# for i in range(h):
#     if(dp[i]!=MAX_NUM):
#         for j in range(n):
#             a,b=ab[j]
#             ind = i+a if i+a<h else -1
#             dp[ind]=min(dp[ind],dp[i]+b)
# print(dp[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
#a = int(input())
# スペース区切りの整数の入力
#b, c = map(int, input().split())
# 文字列の入力
#s = input()
# 出力
#print("{} {}".format(a+b+c, s))

import numpy as np

h, n = map(int, input().split())
inf=2*10**9
a = np.full(n,inf, int)
b = np.full(n,inf, int)
for i in range(0, n):
  a[i], b[i] = map(int, input().split())

dp=np.full(10001,0,int)
dp[0]=0

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

print(dp[h])

Submission status: Accepted

Solution code:
#import time
#t1 = time.time()
h,n = map(int,input().split())
ab = [[int(i) for i in input().split()] for j in range(n)]

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

for i in range(n):
    dp[i][0] = 0
    
for i in range(1,h+1):
    dp[0][i] = ((i+ab[0][0]-1) // ab[0][0]) * ab[0][1]

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

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

h, n = map(int, input().split())
ab = np.array(sys.stdin.read().split(), dtype=np.int64)
aaa = ab[0::2]
bbb = ab[1::2]

dp = np.zeros(10001, dtype=np.int64)
for i in range(1, h + 1):
    dp[i] = (dp[i - aaa] + bbb).min()
print(dp[h])

Submission status: Accepted

Solution code:
import sys
inf = sys.maxsize

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 = [inf for _ in range(h + max([a[i] for i in range(n)]) + 10)] #dp[体力i削るのに必要な魔力]
dp[0] = 0

for i in range(1, len(dp)):
    for j in range(n):
        dp[i] = min(dp[i], dp[max(0, i-a[j])] + b[j])

#print(dp)
print(min(dp[h:]))

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
arr=[]
for _ in range(n):
  arr.append(list(map(int,input().split())))
dp=[10**10]*20001
dp[0]=0
for i in range(20001):
  for j in range(n):
    if i+arr[j][0]>20000:
      continue
    dp[i+arr[j][0]]=min(dp[i+arr[j][0]],dp[i]+arr[j][1])
ans=10**18
for i in range(h,20001):
  ans=min(ans,dp[i])
print(ans)

Submission status: Accepted

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

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

h_map = [-1 for _ in range(h+1)]

h_map[h] = 0
for i in range(h):
  i_map = h - i
  if h_map[i_map] == -1:
    continue
  
  for a, b in ab:
    if (i_map - a) <= 0:
      if h_map[0] != -1:
        h_map[0] = min(h_map[0], h_map[i_map]+b)
      else:
        h_map[0] = h_map[i_map] + b
    else:
      if h_map[i_map - a] != -1:
        h_map[i_map - a] = min(h_map[i_map - a], h_map[i_map]+b)
      else:
        h_map[i_map - a] = h_map[i_map]+b

print(h_map[0])

Submission status: Accepted

Solution code:
from fractions import gcd
# from datetime import date, timedelta
# from heapq import *
import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


def lcm(a, b):
    return a * b / fractions.gcd(a, b)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def modinv(a, mod):
    return modpow(a, mod - 2, mod)


def cnk(a, b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1, MOD) % MOD
    return ret


class UnionFind:
    def __init__(self, n):
        self.sz = [-1 for i in range(n)]

    # 検索
    def find(self, x):
        if self.sz[x] < 0:
            return x
        else:
            self.sz[x] = self.find(self.sz[x])
            return self.sz[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.sz[x] > self.sz[y]:
            x, y = y, x
        self.sz[x] += self.sz[y]
        self.sz[y] = x

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xが含まれている集合のサイズを求める
    def size(self, x):
        return -self.sz[self.find(x)]


def main():   
    h, n = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n)]
    
           
    dp = [float("inf")] * (h + 1)
    dp[0] = 0
    for i in range(1,h+1):
        for j in range(n):
            dp[i] = min(dp[i], dp[max(0, i - ab[j][0])] + ab[j][1])
    print(dp[h])


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




            


    




    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
h, n = map(int, input().split())
a = np.zeros(n, int)#np.emptyの方が少し早い
b = np.zeros(n, int)
for i in range(n):
    a[i], b[i] = map(int, input().split())
    
dp = np.zeros(h+1, int)
for i in range(1, h+1):
    rh = i - a# rhは実際にはH # まずは全ての魔法を使ってみる
    rh[rh<0] = 0 # 魔法を使ってHが0以下になるのであればその魔法で一発で0にできるということ
    dp[i] = np.min(dp[rh]+b)# dp[i]は残りのHPがiのときに必要な最小MP　# bは今回使用した魔法の消費MP

print(dp[h])

Submission status: Accepted

Solution code:
w, h = (int(x) for x in input().split())
ab = []
for _ in range(h):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
 
dp = [10000000000000 for i in range(w+1)]
 
for j in range(w+1):
    for i in range(h):
        if j <= ab[i][0]:
            dp[j] = min(dp[j], ab[i][1])
        else:
            dp[j] = min(dp[j], dp[j-ab[i][0]]+ab[i][1])
 
print(dp[w])

Submission status: Accepted

Solution code:
#import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

## 計算量: H*N

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

inf = float("inf")
dp = [inf for i in range(H+1)] ## i: 体力
dp[0] = 0

for i in range(1, H+1):
  for j in range(N):
    dp[i] = min(dp[i], dp[max(i - AB[j][0], 0)] + AB[j][1])
    
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:
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 = [0 for _ in range(h+1)]

for i in range(1,h+1):
    magic = 10 ** 10
    for j in range(n):
        magic = min(DP[max(0, i-A[j])] + B[j], magic)
    DP[i] = magic

print(DP[-1])

Submission status: Accepted

Solution code:
h,n,*L=map(int,open(0).read().split())
dp=[0]*(h+10100)
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 numpy as np
H, N = list(map(int, input().split()))
A = np.empty(N, int)
B = np.empty(N, int)
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))


DP = np.empty(H+1, int)
DP[0] = 0
for i in range(1, H+1):
    I = i-A;
    I[I<0] = 0
    DP[i] = np.min(DP[I] + B)
    
print(DP[H])

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):
    dpi_1 = dp[np.maximum(i - ab[:, 0], 0)]
    dpi = dpi_1 + ab[:, 1]
    dp[i] = np.min(dpi)
    
print(dp[-1])

Submission status: Accepted

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

H, N = map(int, input().split())
AB = []
for i in range(N):
    a_tmp, b_tmp = map(int, input().split())
    AB.append([a_tmp, b_tmp])

dp=[0]*(H+max(s for s,t in AB))

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

print(dp[H])

Submission status: Accepted

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

dp=[float("inf")]*(h+maA+1)
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:
H,N = map(int,input().split())
p = []
for i in range(N):
    t = list( map( int, input().split() ) )
    p.append(t)

a = max(p)[0]
dp = [10**9] * (H+1+a)
dp[0] = 0

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

print(min(dp[H:H+a]))

Submission status: Accepted

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

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

for ai, bi in magics:
  for i in range(h + max_a - ai):
    if dp[i] != float("inf"):
      dp[i + ai] = min(dp[i] + bi, dp[i + ai])


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

Submission status: Accepted

Solution code:
# ABC153 E - Crested Ibis vs Monster
h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
    aa,bb=map(int,input().split())
    a.append(aa)
    b.append(bb)

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

for i in range(n):
    for j in range(h+1):
        # i番目の魔法を使わない場合
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        # i番目の魔法を使う場合
        dp[i+1][min(j+a[i],h)]=min(dp[i+1][min(j+a[i],h)],dp[i+1][j]+b[i])    
        
print(dp[n][h])

Submission status: Accepted

Solution code:
w, h = (int(x) for x in input().split())
ab = []
for _ in range(h):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])

dp = [0] * (w + max(a for a, b in ab))

for j in range(1, w+1):
    dp[j] = min(dp[j-a]+b for a, b in ab)

print(dp[w])

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,N=map(int,input().split())
a=[]
max_x=-10**10
for i in range(N):
  x,y=map(int,input().split())
  if x>max_x:
    max_x=x
  a.append([x,y])
  
dp = [0] * (H+max_x)
for i in range(0,H+max_x):
    if i==0:
        dp[i]=0
    else:
        dp[i]=min(dp[i-l[0]]+l[1] for l in a )
print(dp[H])

Submission status: Accepted

Solution code:
from sys import stdin, stdout	

def sol2():
	H, N = (int(x) for x in stdin.readline().split())
	dp = [float('inf') for _ in range(H+1)]
	dp[0] = 0
	for line in stdin:
		dmg, cost = [int(x) for x in line.split()]
		for i in range(len(dp)):
			new = min(H, i + dmg)
			dp[new] = min(dp[new], dp[i] + cost)
	stdout.write(str(dp[-1]))

if __name__ == "__main__":
	sol2()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

def resolve():

    hp_max = (10**4)*3

    dp=[-1]*hp_max
    dp[0]=0

    h,n = list(map(int,input().split()))
    a=[0]*n #damage
    b=[0]*n #syouhi

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

    for hp in range((10**4)*2):
        if dp[hp]==-1:
            continue
        for i in range(n):
            nhp = hp+a[i]
            cost = dp[hp]+b[i]
            if dp[nhp]==-1:
                dp[nhp]=cost
            elif cost <= dp[nhp]:
                dp[nhp]=cost

    min_cost=0

    for hp in range(h,hp_max):
        if dp[hp]==-1:
            continue

        cost = dp[hp]

        if min_cost == 0:
            min_cost = cost
        elif cost<min_cost:
            min_cost = cost
    
    print(min_cost)

    return

resolve()

Submission status: Accepted

Solution code:

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

INF=float("inf")
    
dp=([[INF]*(1+h) for i in range(1+n)])


dp[0][0]=0

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

# print(dp)
print(dp[n][h])

Submission status: Accepted

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

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

show_flg=False
show_flg=True

ans=0

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

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

ans=dp[n][h]

print(ans)