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: Runtime Error

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

dp = [None] * (H+1)
dp[0] = 0

for i in range(1, H+1):
  for a, b in AB:
    if dp[i-a] != None:
      if dp[i] != None:
        dp[i] = min(dp[i], dp[i-a] + b)
      else:
        dp[i] = dp[i-a] + b
  
bef = dp[0]
for i, x in enumerate(dp[1:]):
  if x is None:
    dp[i+1] = bef
    if i == len(dp[1:]) - 1:
      dp[H] = None
  else:
    bef = x
    

ans = np.inf
for a, b in AB:
  ans = min(ans, dp[H-a+1] + b)
if dp[H]:
  ans = min(ans, dp[H])
print(ans)

Submission status: Runtime Error

Solution code:
#配るDP
#AtCorder143
def dis_dp(N,H,a_list,b_list):
    #初期化
    inf = float("inf")
    dp = [[inf for i in range(N+100)] for b in range(H+100)]
    dp[0][0] = 0
    #DP
    for i in range(N ):
        for b in range(H + 1):            
            if dp[i+1][b] > dp[i][b]:
                dp[i+1][b] = dp[i][b]#i番目の魔法を使わないケース
            if dp[i+1][min(b + a_list[i], H)] > dp[i+1][b] + b_list[i]:
                dp[i+1][min(b + a_list[i], H)] =  dp[i+1][b] + b_list[i]#i番目の魔法を使うケース,Hを超えるケースも考る
    return dp[N][H]
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)
print(dis_dp(N,H,a_list,b_list))

Submission status: Runtime Error

Solution code:
#配るDP
#AtCorder143
def dis_dp(N,H,a_list,b_list):
    #初期化
    inf = float("inf")
    dp = [[inf for i in range(N+100)] for b in range(H+100)]
    dp[0][0] = 0
    #DP
    for i in range(N ):
        for b in range(H + 1):            
            if dp[i+1][b] > dp[i][b]:
                dp[i+1][b] = dp[i][b]#i番目の魔法を使わないケース
            if dp[i+1][min(b + a_list[i], H)] > dp[i+1][b] + b_list[i]:
                dp[i+1][min(b + a_list[i], H)] =  dp[i+1][b] + b_list[i]#i番目の魔法を使うケース,Hを超えるケースも考る
    return dp[6][100]
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)
print(dis_dp(N,H,a_list,b_list))

Submission status: Runtime Error

Solution code:
#配るDP
#AtCorder143
def dis_dp(N,H,a_list,b_list):
    #初期化
    inf = float("inf")
    dp = [[inf for i in range(N+10)] for j in range(H+10)]
    dp[0][0] = 0
    #DP
    for i in range(N):
        for b in range(H):            
            if dp[i+1][b] > dp[i][b]:
                dp[i+1][b] = dp[i][b]#i番目の魔法を使わないケース
            if dp[i+1][min(b + a_list[i], H)] > dp[i+1][b] + b_list[i]:
                dp[i+1][min(b + a_list[i], H)] =  dp[i+1][b] + b_list[i]#i番目の魔法を使うケース,Hを超えるケースも考る
    return dp[N][H]
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)
print(dis_dp(N,H,a_list,b_list))

Submission status: Runtime Error

Solution code:
#配るDP
#AtCorder143
def chmin(a,b):
    if a>b :
        a = b
        return True
    return False
def dis_dp(N,H,a_list,b_list):
    #初期化
    inf = float("inf")
    dp = [[inf for i in range(N+1)] for j in range(H+1)]
    dp[0][0] = 0
    #DP
    for i in range(1,N):
        for b in range(1,H + 1):
            chmin(dp[i+1][b],dp[i][b])#i番目の魔法を使わないケース
            chmin(dp[i+1][min(b + a_list[i], H)],dp[i+1][j] + b_list[i])#i番目の魔法を使うケース,Hを超えるケースも考慮する
    return dp[N][H]

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)
print(dis_dp(N,H,a_list,b_list))

Submission status: Runtime Error

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

AB.sort(key=lambda x: -(x[0] / x[1]))
# print("#", AB)

memo = [None] * (H + 1)
def dp(arg):
    # print("#", arg)
    if arg <= 0: return 0
    if memo[arg] != None: return memo[arg]
    #
    rets = []
    for i, (Ai, Bi) in enumerate(AB):
        rets.append(Bi + dp(arg - Ai))
    #
    ret = min(rets)
    memo[arg] = ret
    return ret

print(dp(H))
# print("#", memo)

Submission status: Runtime Error

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())
INF = 10**10


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

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

Submission status: Runtime Error

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())
INF = 10**10


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

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

Submission status: Runtime Error

Solution code:
h,n = map(int,input().split())
skills = []
for _ in range(n):
  a,b = map(int,input().split())
  skills.append((a,b))
dp = [-1 for _ in range(h+max(skills) + 1)]
dp[0] = 0
  
for i in range(len(dp)):
  if dp[i] ==-1:
    continue
  for damage,mp in skill:
    if dp[i+mp] < dp[i] + damage:
      dp[i+mp] = dp[i]+damage
print(min(dp[h:]))

Submission status: Runtime Error

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

_,a,b = lst[-1]

mp  = (h//a) * b
h -= h//a * a
lst.sort(key = lambda x:x[2])
for i in lst:
  if lst[i][1] >=h:
    mp += lst[i][2]
    break
print(mp)

Submission status: Runtime Error

Solution code:
H, n = map(int, input().split())
List = [[0 for i in range(4)] for j in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    List[i][0] = b / a
    List[i][1] = b / H
    List[i][2] = a
    List[i][3] = b

def recal():
    for i in range(n):
        b = List[i][3]
        List[i][1] = b / H

sList = sorted(List)
MP = 0
k = 0
while H > 0:
    if sList[k][2] <= H:
        H -= sList[k][2]
        MP += sList[k][3]
        recal()
    else:
        if sList[k + 1][2] <= H:
            if sList[k][1] <= sList[k + 1][0]:
                H -= sList[k][2]
                MP += sList[k][3]
                recal()
                break
            else:
                H -= sList[k + 1][2]
                MP += sList[k + 1][3]
                recal()
                k += 1
        else:
            if sList[k][1] <= sList[k + 1][1]:
                H -= sList[k][2]
                MP += sList[k][3]
                recal()
                break
            else:
                H -= sList[k + 1][2]
                MP += sList[k + 1][3]
                recal()
                k += 1
print(MP)

Submission status: Runtime Error

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

ab=[[0]*2 for i in range(n)]
maxa=0

for i in range(0,n):
  ab[i][0], ab[i][1] = map(int, input().split())
  if maxa<ab[i][0]:
    maxa=ab[i][0]

sab=sorted(ab,key=lambda x:x[0]*10**5-x[1])

ans=[0]*(h+maxa)
maxl=2*10**8

for i in range(1,h+maxa):
  ans[i]=maxl
  for j in range(0,n):
    if i<sab[j][0]:
      break
    if ans[i] > (ans[i-sab[j][0]]+sab[j][1]):
      ans[i] = ans[i-sab[j][0]]+sab[j][1]

print(min(ans[h:h+maxa-1]))

Submission status: Runtime Error

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

ab=[[0]*2 for i in range(n)]
maxa=0

for i in range(0,n):
  ab[i][0], ab[i][1] = map(int, input().split())
  if maxa<ab[i][0]:
    maxa=ab[i][0]

sab=sorted(ab,key=lambda x:-x[0]*10**5+x[1])

ans=[0]*(h+maxa)
maxl=2*10**8

for i in range(1,h+maxa):
  ans[i]=maxl
  for j in range(0,n):
    if (i-sab[j][0]) >= 0:
      if ans[i] > (ans[i-sab[j][0]]+sab[j][1]):
        ans[i] = ans[i-sab[j][0]]+sab[j][1]

print(min(ans[h:h+maxa-1]))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:

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

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

dp = [math.inf] *(H+1)
dp[H] = 0
for a,b in AB:
    for i in range(H,-1,-1):
        if i <= H - a:
            dp[i] = min(dp[i], dp[i+a] + b)
        dp[0] = min(dp[0], min(dp[:a+1]) + b) # if hp is not just 0

print(dp[0])

Submission status: Runtime Error

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

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

dp = [math.inf] *(H+1)
dp[H] = 0
for a,b in AB:
    for i in range(H,-1,-1):
        if i <= H - a:
            dp[i] = min(dp[i], dp[i+a] + b)
        dp[0] = min(dp[0], min(dp[:a+1]) + b) # if hp is not just 0

print(dp[0])

Submission status: Runtime Error

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

magic = [[0] * 2 for i in range(N+1)]

# for i in range(1, N+1):
#    magic[i] = list(map(int, input().split()))

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

for i in range(1, N + 1):
    A, B = map(int, input().split())
    for j in range(1, H + 1):
        old_data = dp[i-1][j]
        new_data = dp[i][j-A] + B
        if (old_data == 0):
            dp[i][j] = new_data
        else:
            dp[i][j] = min(old_data, new_data)

# print(dp)

print(dp[N][H])

Submission status: Runtime Error

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=[[]*(h)]*(n)
dp[0][0]=b[0]
for i in range(1,n):
    dp[i][0]=min(b[0:i+1])
for i in range(0.h):
    dp[0][i]=

Submission status: Runtime Error

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 for i in range(w+1)]

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

print(dp[w])

Submission status: Runtime Error

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

for i in range(N):	
  ATK.append(list(map(int, input().split())))
mp_min = [0]
for hp in range(1, H+1):
  mp_min.append(min([mp_min[max(0, hp-ATK[i][0])] + ATK[i][1] for i in range(N)]))

  print(mp_min)

print(mp_min[-1])

Submission status: Runtime Error

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

for i in range(N):	
  ATK.append(list(map(int, input().split())))
m = min([ATK[i][1] for i in range(N)])
mp_min = [0]
if m < H:
  for hp in range(1, H+1):
    mp_min.append(min([mp_min[max(0, hp-ATK[i][0])] + ATK[i][1] for i in range(N)]))

    #print(mp_min)

  print(mp_min[-1])
else:
  print(min([ATK[i][1] for i in range(N) if ATK[i][0] >= H]))

Submission status: Runtime Error

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

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

dp = [math.inf] *(H+1)
dp[H] = 0
for a,b in AB:
    for i in range(H,-1,-1):
        if i <= H - a:
            dp[i] = min(dp[i], dp[i+a] + b)
        dp[0] = min(dp[0], min(dp[:a+1]) + b) # if hp is not just 0

print(dp[0])

Submission status: Runtime Error

Solution code:
import numpy as np

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=np.array([[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: Runtime Error

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((a,b))
ab.sort()
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)

Submission status: Runtime Error

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=[]
b=[]
for i in range(n):
    x,y=LI()
    ab.append((a,b))
ab.sort()
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)

Submission status: Runtime Error

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=[]
b=[]
for i in range(n):
    x,y=LI()
    a+=[x]
    b+=[y]
M=max(a)

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

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

ans=dp[n][h]

print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pint;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define IREP(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LMAX LLONG_MAX
#define LMIN LLONG_MIN
template<typename T> inline void chmin(T &a, T b){ if(a > b) a = b; }
template<typename T> inline void chmax(T &a, T b){ if(a < b) a = b; }
template<typename T> inline void xch(T &a, T &b){ T w = a; a = b; b = w; }


int main() {
    int H, N;
    cin >> H >> N;
    int A[N], B[N];
    REP(i, N){
        cin >> A[i] >> B[i];
    }
    ll dp[10001];
    REP(i, 10001) dp[i] = (ll)1e10;
    dp[0] = 0;
    REP(i, N){
        REP(j, 10001){
            int next = min(j + A[i], H);
            dp[next] = min(dp[next], dp[j] + B[i]);
        }
    }
    cout << dp[H] << endl;
    return 0;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

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

sorted_a_list = []
attack_list = [{'damage' : 0, 'cost' : 0, 'damage_p_cost' : 0}]
min_cost = 0
sum_cost = 0
rest_hp = 0

h , n = map(int, input().split())
for i in range(n):
    a , b = map(int, input().split())
    attack_list.append({'damage' : a, 'cost' : b, 'damage_p_cost' : a/b})
    if(min_cost > b or min_cost == 0):
        min_cost = b
attack_list.pop(0)

sorted_a_list = sorted(attack_list, key=lambda x:x['damage_p_cost'], reverse=True)

# print(sorted_a_list)

def batle(hp):
    for i in sorted_a_list:
        if(hp >= i['damage']):
            sum_cost = i['cost'] * int(hp / i['damage'])
            hp = hp % i['damage']
            if(hp == 0):
                return sum_cost
    sum_cost = sum_cost + min_cost
    return sum_cost
    

if __name__ == '__main__':
    ans = batle(h)
    print(ans)

Submission status: Runtime Error

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


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [0] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b if amt - a >= 0 for a, b in magic]
    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)

Submission status: Runtime Error

Solution code:
import numpy as np
h,n=map(int,input().split())
a=np.empty((3,n))
for i in range(n):
  aa,bb=map(int,input().split())
  a[0,i]=aa
  a[1,i]=bb
  a[2,i]=aa/bb
a=a[np.argsort(a[:,2])]
c=0
while h>0:
  for i in range(n):
    if a[0,i]<h or a[0,i]==a[0].min():
    	h-=a[1,i]
    	c+=a[0,i]
    	break
print(int(c))

Submission status: Runtime Error

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

dp = []
dp[0] = 0
for i in range(h+max_cost+1):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))

Submission status: Runtime Error

Solution code:
INF = 10**10
def solve(h, n, a, b):
    ab = sorted(zip(a, b), key=lambda _:_[0]/_[1], reverse=True)
    dp = [-1] * h
    def f(h):
        best = INF
        for x, y in ab:
            if h-x <= 0:
                score = y
            else:
                if dp[h-x] == -1:
                    dp[h-x] = f(h-x)
                score = y + dp[h-x]
            if score < best:
                best = score
            else:
                break
        return best
    return f(h)

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())
print(solve(h, n, a, b))

Submission status: Runtime Error

Solution code:
import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    H, N = map(int,input().split())
    M = [list(map(int,input().split())) for k in range(N)]

    dp = [10**9 for k in range(H+1)]
    dp[0] = 0
    for e in M:
        A, B = e[0], e[1]
        for k in range(A+1):
            dp[k] = min(dp[k],B)
        for k in range(A+1,H+1):
            dp[k] = min(dp[k],dp[k-A]+B)

    print(dp[H])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def f(k):
    if k<=0:
        return 0
    elif memo[k]>0:
        return memo[k]
    else:
        rr=[]
        for i in range(n):
            rr.append(brr[i]+f(k-arr[i]))
        memo[k]=min(rr)
        return memo[k] 

memo=defaultdict(int)
h,n=map(int,input().split())
arr=[]
brr=[]
for _ in range(n):
    a,b=map(int,input().split())
    arr.append(a)
    brr.append(b)

print(f(h))

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
using namespace std;



int main() {
	long long int n, h;
	cin >> h;
	cin >> n;

	vector<pair<long long int, long long int> > v;
	vector<long long int> dp(h+1, 1e17);
	dp[0] = 0;
	for (long long int i=0; i<n; i++) {
		long long int a, b;
		cin >> a;
		cin >> b;
		v.push_back(make_pair(a, b));
	}
	
	long long int zero = (long long int) 0;	
	for (int i=0; i<h+1; i++) {
		for (int j=0; j<n; j++) {

			dp[i] = min(dp[i], dp[max(zero, i-v[j].first)] + v[j].second);
		}
	}


	cout << dp[h] << "\n";
	
	return 0;
			
}

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

def solve(hp, i, A, B, memo):
    if hp <= 0:
        return 0

    if i >= len(A):
        return sys.maxsize

    if memo[hp][i] != -1:
        return memo[hp][i]

    res = solve(hp - A[i], i, A, B, memo) + B[i]
    res = min(res, solve(hp - A[i], i + 1, A, B, memo) + B[i])
    res = min(res, solve(hp, i + 1, A, B, memo))

    memo[hp][i] = res
    return res

def main():
    H, N = map(int, input().split())
    A, B = [], []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    memo = defaultdict(lambda: defaultdict(lambda: -1))
    print(solve(H, 0, A, B, memo))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

# モンスターの体力を0にすることができる魔力の最小値
dp = [[10**9] * (H+1) for _ 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):
        # j 倒すモンスターのHP
        a, b = AB[i-1]
        # a 攻撃力
        # b 消耗する魔力
        h = math.ceil(j/a)
        # h AB[i]のみを使った場合に必要な魔力
        dp[i][j] = min(dp[i][j], h*b, dp[i-1][j], dp[i-1][j-a]+b)

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

Submission status: Runtime Error

Solution code:
def main():
    h, n = map(int, input().split())
    magic_list = []

    for _ in range(n):
        a, b = map(int, input().split())
        magic_list.append((a, b))

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    # 1-origin
    dp = [0] * (h + 1)

    # time O(HN)
    for hp in range(1, h + 1):
        dp[hp] = min(dp[hp - attack] + mp for attack, mp in magic_list)

    return dp[h]


main()

Submission status: Runtime Error

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

for i in box:
  a.append(i[0])
  b.append(i[1])
  box2.append(i[0]/i[1])
  
while h > max[a]:
  h -= a[index(max(box2))]
  b += b[index(max(box2))]

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    maxA = max(A)
    HmaxA = H + maxA
    minB = min(B)
    dp = [max(B) * HmaxA] * (HmaxA + 1)
    dp[0] = 0
    for h in range(HmaxA):
        for n in range(N):
            dp[h + 1] = min(dp[h + 1], dp[h] + minB)
            hp = h + A[n]
            if hp <= HmaxA:
                dp[hp] = min(dp[hp], dp[h] + B[n])
        print(h, dp)
    return min(dp[H:HmaxA+1])

print(ibis(H, A, B))

Submission status: Runtime Error

Solution code:
h, n = list(map(int, input().split()))
ab = []
for i in range(n):
    a, b = list(map(int, input().split()))
    ab.append((a, b))
ab.sort(key=lambda ab: (ab[0]/ab[1], -ab[0]), reverse=True)

import sys
sys.setrecursionlimit(1500)

mem = [-1 for i in range(h)]
def solve(h):
    best = float('inf')
    for a,b in ab:
        if h - a <= 0:
            val = b
        else:
            if mem[h - a] != -1:
                val = b + mem[h - a]
            else:
                mem[h - a] = solve(h - a)
                val = b + mem[h-a]
        if val < best:
            best = val
        else:
            break
    return best

print(solve(h))