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:
def resolve():
    h, n = map(int, input().split())
    lab = []
    while True:
        try:
            a, b = map(int, input().split())
            lab.append([a, b])
        except:
            break
    cost = [0] * (h+1)
    for i in range(1, h+1):
        mb = 10 ** 8
        for j in range(n):
            if i < lab[j][0]:
                mb = min(mb, lab[j][1])
            else:
                mb = min(mb, cost[i - lab[j][0]] + lab[j][1])
        cost[i] = mb
    print(cost[h])
resolve()

Submission status: Accepted

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


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

    dp = [[float("inf") for j in range(H+1)] for i in range(N+1)]
    for i in range(N):
        for j in range(H+1):
            if j <= A[i][0]:
                dp[i+1][j] = min(dp[i][j], A[i][1])
            else:
                dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i][0]] + A[i][1])
#    [print(d) for d in dp]
    print(dp[N][H])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

skills=[]
for _ in range(n):
    x,y=map(int,input().split())
    skills.append((x,y))

INF=float("inf")

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

for a,b in skills:
    for hh in range(h,0,-1):
        if hh-a>=0:
            dp[hh-a]=min(dp[hh-a],dp[hh]+b)
        else:
            dp[0]=min(dp[0],dp[hh]+b)          
            
print(dp[0])

Submission status: Accepted

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

h,n,*ab=map(int,read().split())
a=np.array(ab[::2])
b=np.array(ab[1::2])

magic=np.zeros(h+1,dtype=np.int64)
for i in range(1,1+h):
  magic[i]=np.min(magic[np.maximum(i-a, 0)]+b)
print(magic[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())
    l.append((a,b))
d=[0]*10005
for i in range(h):
    for j in l:
        a,b=j[0],j[1]
        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)

Submission status: Accepted

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"
exit $?
'''
import sys
import math


def _ia():
    return [int(x) for x in sys.stdin.readline().strip().split()]


h, n = _ia()
ab = [_ia() for _ in range(n)]
m_max = math.ceil(h / ab[0][0]) * ab[0][1]
h1 = h + 1
dp = [
    [0] + [m_max + 1] * h for i in range(n + 1)
]
for i in range(n):
    ai, bi = ab[i]
    for j in range(1, h1):
        if j >= ai:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - ai] + bi, dp[i + 1][j - ai] + bi)
        else:
            dp[i + 1][j] = min(dp[i][j], bi)
print(dp[n][h])

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readlines()

h, n = map(int, inputs[0].split())
AB = [tuple(map(int, s.split())) for s in inputs[1:]]

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

Submission status: Accepted

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

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

AB = []

for i in range(N):
	a,b = map(int, input().split())
	AB.append([a,b])
AB = np.array(AB)
A = AB[:,0]
B = AB[:,1]
dp = np.array([0]*(H+1))
for i in range(1, H+1):
	dp[i] = np.min(dp[np.maximum(i - A, 0)]+B)

print(dp[H])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

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

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

DP = [1 << 32-1] * (H+10**4 + 10**4)
DP[0] = 0

for i in range(H+10**4):
    for a, b in AB:
        DP[i + a] = min(DP[i+a], DP[i] + b)

print(min(DP[H:]))

Submission status: Accepted

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

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

AB = []

for i in range(N):
	a,b = map(int, input().split())
	AB.append([a,b])
AB = np.array(AB)
A = AB[:,0]
B = AB[:,1]
dp = np.array([0]*(H+1))
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:
INF=10**10
def main():
  H,N=map(int,input().split())
  AB=[]
  for i in range(N):
    AB.append(list(map(int,input().split())))
  dp=[INF]*(H+1)
  dp[0]=0
  for a,b in AB:
    for k in range(H+1):
      tmp=k-a
      if tmp<0:
        tmp=0
      need_magic=dp[tmp]+b
      if need_magic<dp[k]:
        dp[k]=need_magic
  print(dp[H])
main()

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,n = LI()
dp = [inf]*(h+1)
dp[0] = 0
ab = [LI() for _ in range(n)]
for i in range(h+1):
    for a,b in ab:
        if i + a <= h:
            dp[i+a] = min(dp[i+a],dp[i]+b)
        else:
            dp[-1] = min(dp[-1],dp[i]+b)
print(dp[-1])

Submission status: Accepted

Solution code:
# E
# -*- coding: utf-8 -*-
H, N = map(int, input().split())
A_list = []
B_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)

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

def test_func(dp, A_list, B_list, i, N):
    return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))


for i in range(1, H + 1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

print(dp[-1])

Submission status: Accepted

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

def dp(h,n,ls):
    table=[[0]*(h+1) for i in range(n)]
    atk,cost=ls[0][0],ls[0][1]
    for x in range(h+1):
        cost_of_this = cost*((x-1)//atk+1) if x!=0 else cost
        table[0][x]=cost_of_this
    for i in range(1,n):
        atk,cost=ls[i][0],ls[i][1]
        for j in range(h+1):
            if atk>=j:
                table[i][j]=min(table[i-1][j], cost)
            else:
                table[i][j]=min(table[i-1][j], table[i][j-atk]+cost)
    return(table[-1][-1])

ans=dp(h,n,ls)
print(ans)

Submission status: Accepted

Solution code:
H,N = map(int,input().split())
MAXH = H+10000
DP = [float("inf")]*MAXH
DP[0] = 0
for i in range(N):
    a,b = map(int,input().split())
    for j in range(MAXH-a):
        if j>H+a:break
        DP[j+a] = min(DP[j+a],DP[j]+b)
print(min(DP[H:]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h, n = map(int, input().split())
ab = []
ma = 0
for i in range(n):
    a, b = map(int, input().split())
    ma = max(ma, a)
    ab.append([a, b])

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

for i, (a, b) in enumerate(ab):
    dp[i + 1][0] = 0
    for j in range(h + ma + 1):
        if j >= a:
            dp[i + 1][j] = min(dp[i + 1][j - a] + b, dp[i][j])
        else:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

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 = 10 **15
dp = [[INF]*(10**4+1) for i in range(10**3+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:
H,N=map(int,input().split())
ABC=[]
for _ in range(N):
  a,b=map(int,input().split())
  ABC.append((a,b,a/b))
A=[ABC[i][0] for i in range(N)]
B=[ABC[i][1] for i in range(N)]
dp=[[float('inf')]*(H+1) for i in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
  
for i in range(N):
  for j in range(1,H+1):
    if j-A[i]>=0:
      dp[i+1][j]=min(dp[i][j],dp[i+1][j-A[i]]+B[i])
    else:
      dp[i+1][j]=min(dp[i][j],dp[i+1][0]+B[i])
print(dp[N][H])

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
inf=10**4+2*10**3
dp=[10**8]*(inf)
dp[0]=0
for i in range(inf):
    for j in range(n):
        if i-a[j][0]>=0:
            dp[i]=min(dp[i],dp[i-a[j][0]]+a[j][1])
print(min(dp[h:]))

Submission status: Accepted

Solution code:
#coding:utf-8
 
def main():
    h, n = map(int, input().split())
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    
    inf = 100000000000
    # indexがモンスターに与えたダメージで、中身がトキのダメージ
    damages = [inf for _ in range(100000)]
    damages[0] = 0
    pre_damage = -1
    for i in range(h):
        if damages[i] == inf:
            continue
        for j in range(n):
            new_damage = ab[j][0]
            if damages[i + new_damage] > damages[i] + ab[j][1]:
                damages[i + new_damage] = damages[i] + ab[j][1]
        
 
    print(min(damages[h:]))
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:
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, N = map(int, readline().split())
AB = np.array([list(map(int,
                        readline().split())) for _ in range(N)],
              dtype=np.int64)

A = AB[:, 0]
B = AB[:, 1]

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

print(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)]
dp = [INF for i in range(H + 1)]

dp[0] = 0

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

print(dp[-1])

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])
INF = 10**15
dp = [[INF]*(2*10**4+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
 
for i in range(N):
    for j in range(1,2*10**4+1):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-AB[i][0]]+AB[i][1])
        
ans = float('inf')
for i in range(H,2*10**4+1):
    ans = min(ans,dp[N][i])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h, n = map(int, input().split())
ab = []
ma = 0
for i in range(n):
    a, b = map(int, input().split())
    ma = max(ma, a)
    ab.append([a, b])
ab.sort(reverse=True)
INF = 10 ** 9
dp = [[INF for i in range(h + ma + 1)] for j in range(n+1)]
ans = INF
for i, (a, b) in enumerate(ab):
    dp[i + 1][0] = 0
    for j in range(a, h + ma + 1):
        # print(dp[i + 1][j - a] + b)
        dp[i + 1][j] = min(dp[i + 1][j - a] + b, dp[i][j])
        if j >= h:
            ans = min(ans, dp[i + 1][j])
# print(dp)
print(ans)

Submission status: Accepted

Solution code:

H, N = list(map(int, input().split()))
ab_list = []
max_a = -float("inf")
for _ in range(N):
    a, b = list(map(int, input().split()))
    ab_list.append((a, b))
    max_a = max(max_a, a)

dp_table = [[0] + [float("inf")] * H for _ in range(N + 1)]

for i in range(1, N + 1):
    a, b = ab_list[i - 1]
    next_j = 0
    # for j in range(H + max_a):
    over_min_cost = float("inf")
    for j in range(H + 1):
        # 攻撃jをしない場合
        before_best_cost = dp_table[i - 1][j]
        dp_table[i][j] = min(dp_table[i][j], before_best_cost)
        # 攻撃jをする場合
        if j - a >= 0:
            cost = dp_table[i - 1][j - a] + b
            min_cost = min(before_best_cost, cost)

            cost = dp_table[i][j - a] + b
            min_cost = min(min_cost, cost)

            dp_table[i][j] = min(dp_table[i][j], min_cost)

        if j + a > H:
            cost = dp_table[i - 1][j] + b
            dp_table[i][H] = min(dp_table[i][H], cost)
            cost = dp_table[i][j] + b
            dp_table[i][H] = min(dp_table[i][H], cost)
            dp_table[i][H] = min(dp_table[i][H], dp_table[i - 1][H])

ans = dp_table[-1][H]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

h,n = mii()
ab = llint(n)

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

dp[h] = 0

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

print(dp[0])

Submission status: Accepted

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

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

INF=float("inf")

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

for aa,bb in zip(a,b):
    for hh in range(h,0,-1):
        if hh-aa>=0:
            dp[hh-aa]=min(dp[hh-aa],dp[hh]+bb)
        else:
            dp[0]=min(dp[0],dp[hh]+bb)
            
print(dp[0])
# print(dp)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h,n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

inf = 10**9
dp = [inf]*(h+1)
dp[0] = 0
for i in range(n):
    for j in range(h+1):
        d = min(j+ab[i][0], h)
        dp[d] = min(dp[d], dp[j]+ab[i][1])

res = dp[h]
print(res)

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

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



#print(dp)
print(dp[N][H])
                    
#dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-1-a[i]]
#w = c(6,4,3,2)		# 重量
#v = c(19,15,12,8)	# 価値
#f = matrix(0, 5, 21)
#for(n in 1:4) {
#  for(T in 0:20) {
#    f[n+1,T+1] = f[n-1+1,T+1]
#    if(T/w[n] < 1) next          ### for 文はCと違い、1回は必ず実行される
#    for (j in 1:(T/w[n])) {
#       f[n+1,T+1] = max(f[n+1,T+1], j*v[n] + f[n-1+1,T-j*w[n]+1])
#    }
#  }
#}

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 = [[10**12 for i in range(H+1)]
          for i in range(N+1)]
    # dp = [0 for _ in range(H + 2)]

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

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

    for i in range(N):
        # dp_tmp = [0] * (H + 2)
        for h in range(H+1):
            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][h], B[i])

    print(dp[N][-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,n = map(int, input().split( ))
m = []
mxa = 0
for _ in range(n):
    ai,bi = map(int, input().split( ))
    m.append((ai,bi))
    mxa = max(mxa,ai)
inf = 10**10
dp = [inf for _ in range(h+1+mxa)]
dp[0] = 0
for i in range(h+mxa):
    for j in range(n):
        if i+m[j][0]<=h+mxa:
            dp[i+m[j][0]] = min(dp[i+m[j][0]],dp[i]+m[j][1])
print(min(dp[h:]))

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")] * (2 * 10000 + 1)
dp[0] = 0
for i in range(h):
    for j in range(n):
        if (i + a[j]) > 2 * 10000:
            dp[2 * 10000] = min(dp[2 * 10000], dp[i] + b[j])
            continue
        dp[i + a[j]] = min(dp[i + a[j]], dp[i] + b[j])

ans = float('inf')
for j in range(h, 2 * 10000 + 1):
    ans = min(ans, dp[j])
print(ans)

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) for _ in range(N+1)]
dp[0][0] = 0

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

Submission status: Accepted

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

inf=float("inf")
dp=[inf]*(H+1)
dp[0]=0
ans=inf
for i in range(N):
    A,B=AB[i]
    for j in range(max(0,H-A+1)):
        dp[j+A]=min(dp[j+A],dp[j]+B)
    for j in range(max(0,H-A+1),H):
        ans=min(ans,dp[j]+B)
ans=min(ans,dp[H])

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import bisect

h, n = map(int, list(input().split()))

ab = []
max_a = 0
for _ in range(n):
    ab.append(list(map(int, list(input().split()))))
    max_a = max(max_a, ab[-1][0])

dp = [int(1e9)] * int(1e6)
checked = [False] * int(1e6)
dp[0] = 0

sorted_list = [0]
while len(sorted_list) > 0:
    v = sorted_list.pop(0)
    
    if v > h:
        break
    
    for i in range(n):
        if checked[v + ab[i][0]] == False:
            bisect.insort_right(sorted_list, v + ab[i][0])
            checked[v + ab[i][0]] = True
        dp[v + ab[i][0]] = min(dp[v + ab[i][0]], dp[v] + ab[i][1])
    
print(min(dp[v-1:]))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, N = map(int, readline().split())
m = map(int, read().split())
AB = zip(m, m)

INF = 10**18

dp = [INF] * (H + (10**4))
dp[0] = 0
for a, b in AB:
    for n in range(H):
        if dp[n + a] > dp[n] + b:
            dp[n + a] = dp[n] + b

print(min(dp[H:]))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)

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

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


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


AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
bestA, bestB = AB[0]

print(f(H))

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((b/a,a,b))

dp=[100000000 for i in range(h+1)]
dp[0]=0
for i in range(h):
    for q in range(n):
        power=L[q][1]
        magic=L[q][2]
        dp[min(h,i+power)]=min(dp[min(h,i+power)],dp[i]+magic)

print(dp[h])

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]*(10**4+1) for _ in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
mi=10**9
for i in range(N):
  for w in range(10**4+1):
    dp[i+1][w]=min(dp[i+1][w],dp[i][w])
    if w-AB[i][0]>=0:
      dp[i+1][w]=min(dp[i+1][w],dp[i + 1][w - AB[i][0]] + AB[i][1])
for i in range(H,10**4+1):
  mi = min(mi,dp[N][i])
print(mi)

Submission status: Accepted

Solution code:
from math import ceil, floor

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

if n == 1:
  print(ceil(h/l[0][0]) * l[0][1])
  exit(0)

dp = [ceil(hp/l[0][0]) * l[0][1] for hp in range(h + 1)]

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

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

inf = 10**12
dp = [[inf for j in range(H+1)] for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

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

print(dp[N][H])

Submission status: Accepted

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

D = [float("inf")] * (h+10**4+3)
D[0] = 0
for j in range(n):
    for i in range(len(D)):
        D[i] = min(D[i],D[i-A[j][0]] + A[j][1])
    # print(D[:20])
# print(D[:20])
print(min(D[h:]))

# a = float("inf")
# for i in range(n):
#     for j in range(n):
#         for k in range(h//A[i][0]+1):
#             b = A[i][1] * k + A[j][1] * max(0,-((-h+k*A[i][0])//A[j][0]))
#             a = min(a,b)
#             print(A[i][1] , k , A[j][1] , max(0,-((-h+k*A[i][0])//A[j][0])))
#             print(i,j,k,a)
        
# print(a)

# for i in range(n):
#     A[i].append(A[i][0]/ A[i][1])
# A.sort(reverse=True)
# A.sort(key=lambda x:x[2], reverse=True)
# print(A)
# a = 0
# while h > 0:
#     i=0
#     k = h//A[i][0]
#     h -= k * A[i][0]
#     a += k * A[i][1]
#     print(h)
#     if h > 0:
#         for i in range(n):
#             A[i][0] = min(A[i][0], h)
#             A[i][2] = A[i][0] / A[i][1]
#         A.sort(reverse=True)
#         A.sort(key=lambda x:x[2], reverse=True)
#     print(A)
# print(a)

Submission status: Accepted

Solution code:
def main():
    H,N = map(int, input().split())
    weight = list(); value = list()
    for n in range(N):
        temp = input().split()
        weight.append(int(temp[0]))
        value.append(int(temp[1]))
    
    inf = float("inf")
    dp = [[inf for i in range(H+max(weight)+1)] for j in range(N+1)]
    for i in range(N+1): dp[i][0] = 0
    for i in range(N):
        for h in range(H+max(weight)+1):
            if(weight[i] <= h):
                dp[i+1][h]=min(dp[i][h-weight[i]]+value[i], dp[i+1][h-weight[i]]+value[i], dp[i][h])
            else:
                dp[i+1][h]=dp[i][h]
    res = int(min(dp[N][H:]))
    print(res)



if __name__ == "__main__":
    main()

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):
    ans = 0
    abc = [(a/b, b, a) for a, b in AB]

    abc.sort(key=lambda x: x[1])
    abc.sort(key=lambda x: x[2])
    abc.sort(key=lambda x: x[0], reverse=True)
    # ri = set()
    # mm = INF
    # for i in range(N):
    #     if abc[i][1] >= mm:
    #         ri.add(i)
    #     else:
    #         mm = abc[i][1]
    # ri = set(ri)
    # abc_ = []
    # for i in range(N):
    #     if i not in ri:
    #         abc_.append(abc[i])
    # error_print(abc)
    # abc = abc_
    # error_print(abc)

    HD = defaultdict(lambda : INF)
    HD[H] = 0
    _, b, a = abc[0]
    for i in range(1, dc(H, a)+1):
        HD[H - i*a] = i*b
    for _, b, a in abc[1:]:
        for k, v in reversed(list(HD.items())):
            for i in range(1, dc(k, a)+1):
                if HD[k - i*a] > v+i*b:
                    HD[k- i*a] = v+i*b
                else:
                    break
    ans = INF
    for k, v in HD.items():
        if k <= 0:
            ans = min(ans, v)


    return ans


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

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

for i in range(n):
    for j in range(1, h+1):
        if j - lst[i][0] < 0:
            dp[j] = min(dp[0] + lst[i][1], dp[j])
        else:
            dp[j] = min(dp[j - lst[i][0]] + lst[i][1], dp[j])

print(dp[h])

Submission status: Accepted

Solution code:
H,N = map(int,input().split(" "))
lis = []
lis_append = lis.append
dp = [2**50 for _ in range(H+1)]
ans = 2**60
for i in range(N):
    a,b = map(int,input().split(" "))
    if a >= H:
        ans = min(ans,b)
    lis_append([a,b])

dp[0] = 0
for i in range(H+1):
    for a,b in lis:
        if i + a <= H:
            dp[i+a] = min(dp[i+a],dp[i]+b)
        else:
            dp[H] = min(dp[H],dp[i]+b)

ans = min(ans,dp[H])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

H, N = map(int, input().split())
A, B = np.zeros(N, dtype='int'), np.zeros(N, dtype='int')
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b

dp = np.zeros(H, dtype='int')
minimum_cost_magic = np.argmin(B)
minA, minB = A[minimum_cost_magic], B[minimum_cost_magic]
dp[:minA] = minB
for h in range(minA, H):
    mincost = 10*dp[h-1]
    dp_minusAmj = dp[h - A]
    dp_minusAmj[h - A < 0] = 0
    dp[h] = np.min(dp_minusAmj + B)

print(dp[H-1])