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=acinput()
s=[]

mmp=-1
for i in range(N):
    tmp = acinput()
    #tmp.append(tmp[0]/tmp[1])
    s.append(tmp)
    mmp=max(mmp,tmp[0])
#s=sorted(s,reverse=True,key= lambda x:x[2])

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

for i in range(1,H+1):
    dp[0][i]=int(np.ceil(i/s[0][0]))*s[0][1]

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

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

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

Submission status: Runtime Error

Solution code:
H,N=acinput()
s=[]

mmp=-1
for i in range(N):
    tmp = acinput()
    #tmp.append(tmp[0]/tmp[1])
    s.append(tmp)
    mmp=max(mmp,tmp[0])
#s=sorted(s,reverse=True,key= lambda x:x[2])

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

for i in range(1,H+1):
    dp[0][i]=int(np.ceil(i/s[0][0]))*s[0][1]

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

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

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

Submission status: Runtime Error

Solution code:
H,N=acinput()
s=[]

mmp=-1
for i in range(N):
    tmp = acinput()
    #tmp.append(tmp[0]/tmp[1])
    s.append(tmp)
    mmp=max(mmp,tmp[0])
#s=sorted(s,reverse=True,key= lambda x:x[2])

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

for i in range(1,H+1):
    dp[0][i]=int(np.ceil(i/s[0][0]))*s[0][1]

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

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

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

Submission status: Runtime Error

Solution code:
H,N=acinput()
s=[]

mmp=-1
for i in range(N):
    tmp = acinput()
    #tmp.append(tmp[0]/tmp[1])
    s.append(tmp)
    mmp=max(mmp,tmp[0])
#s=sorted(s,reverse=True,key= lambda x:x[2])

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

for i in range(1,H+1):
    dp[0][i]=int(np.ceil(i/s[0][0]))*s[0][1]

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

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

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

Submission status: Runtime Error

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

dp=[0]+[None]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=[0]+[None]*H
    for j in range(A,H+1):
        if dp[j]==None:
            if ndp[j-A]!=None:
                ndp[j]=ndp[j-A]+B
            continue
        
        if ndp[j-A]==None:
            if dp[j]!=None:
                ndp[j]=dp[j]
            
            continue

        ndp[j]=min(ndp[j-A]+B,dp[j])

    for j in range(H-A+1,H+1):
        if ndp[j]==None:
            continue

        if ndp[-1]!=None:
            ndp[-1]=min(ndp[j]+B,ndp[-1])
        else:
            ndp[-1]=ndp[j]+B

    dp=ndp

print(dp[-1])

Submission status: Runtime Error

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

dp=[0]+[None]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=[0]+[None]*H
    for j in range(A,H+1):
        if dp[j]==None:
            if ndp[j-A]!=None:
                ndp[j]=ndp[j-A]+B
            continue
        
        if ndp[j-A]==None:
            if dp[j]!=None:
                ndp[j]=dp[j]
            
            continue

        ndp[j]=min(ndp[j-A]+B,dp[j])

    for j in range(H-A+1,H+1):
        if ndp[j]==None:
            continue

        if ndp[-1]!=None:
            ndp[-1]=min(ndp[j]+B,ndp[-1])
        else:
            ndp[-1]=ndp[j]+B

    dp=ndp
    print(dp)

print(dp[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10000)

import numpy as np

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


def search(i,x):
    global s,dp
    #print(i,x)
    if x<=0:
        return 0
    if dp[i][x]>=0:
        return dp[i][x]
    
    tmp=search(i-1,x)
    a,b=s[i]
    tmp=min(search(i,x-a)+b,tmp)
        
    dp[i][x]=tmp
    return tmp

H,N=acinput()
s=[]

mmp=-1
for i in range(N):
    tmp = acinput()
    #tmp.append(tmp[0]/tmp[1])
    s.append(tmp)
    mmp=max(mmp,tmp[0])
#s=sorted(s,reverse=True,key= lambda x:x[2])

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

for i in range(1,H+1):
    dp[0][i]=int(np.ceil(i/s[0][0]))*s[0][1]
dp[0][0]=0


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

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

Submission status: Runtime Error

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

dp=[0]+[None]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=[0]+[None]*H
    for j in range(A,H+1):
        if ndp[j]==None:
            if ndp[j-A]!=None:
                ndp[j]=ndp[j-A]+B
            continue
        
        if ndp[j-A]==None:
            if ndp[j]!=None:
                ndp[j]=dp[j]
            
            continue

        ndp[j]=min(ndp[j-A]+B,dp[j])

    for j in range(H-A+1,H+1):
        if ndp[j]==None:
            continue

        if ndp[-1]!=None:
            ndp[-1]=min(ndp[j]+B,ndp[-1])
        else:
            ndp[-1]=ndp[j]+B

    dp=ndp

print(dp[-1])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=1000)
def fx(H):
  if H <= 0:
    return 0
  arr = []
  for i in range(len(atk)):
    b = fx(H - atk[i]) + MP[i]
    arr.append(b)   
  return min(arr)

a = fx(H)
print(a)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

#@lru_cache(maxsize=1000)
def fx(H,atk,MP):
  if H <= 0:
    return 0
  arr = []
  for i in range(len(atk)):
    b = fx(H - atk[i],atk,MP) + MP[i]
    arr.append(b)   
  return min(arr)
  
H,N = map(int,input().split())
atk=[]
MP=[]
for i in range(N):
  n,a=input().split()
  atk.append(int(n))
  MP.append(int(a))

a = fx(H,atk,MP)

print(a)

Submission status: Runtime Error

Solution code:
def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(10111):
    dp[index]=min(dp[index],dp[i]+b)
for i in range(h,111111):
  ans=min(ans,dp[i])
print(ans)

Submission status: Runtime Error

Solution code:
def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*11111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(10111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left
INF = float('inf')

H, N=map(int, input().split())
dp = [0 for i in range(H + 1)]

hm = list(list(map(int, input().split())) for i in range(N))

for i in range(1, H+1):
    dp[i] = min(list(dp[i - h] + m for h, m in hm))
print(dp[H])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left
INF = float('inf')

H, N=map(int, input().split())
dp = [0 for i in range(H + 10)]

hm = list(list(map(int, input().split())) for i in range(N))

for i in range(1, H+1):
    dp[i] = min(list(dp[i - h] + m for h, m in hm))
print(dp[H])

Submission status: Runtime Error

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

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)

for i in range(n):
  dp[a[i]]=b[i]
  #print(dp)
for i in range(1,h+1):
  if dp[i]==INF:
    #dp[i]=min(dp[i],dp[i-1])
    #print(dp)
    continue
  for j in range(n):
    if i+a[j]<=h:
      dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j])
      #print(dp)
    else:
      dp[h]=min(dp[h],dp[i]+b[j])
      #print(dp)
  #dp[i]=min(dp[i],dp[i-1])
  #print(dp)
print(dp[h])

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10000)

import numpy as np

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


def search(i,x):
    global s,dp
    #print(i,x)
    if x<0:
        return 0
    if dp[i][x]>=0:
        return dp[i][x]
    
    tmp=search(i-1,x)
    a,b=s[i]
    tmp=min(search(i,x-a)+b,tmp)
        
    dp[i][x]=tmp
    return tmp



H,N=acinput()
s=[]


for i in range(N):
    tmp = acinput()
    #tmp.append(tmp[0]/tmp[1])
    s.append(tmp)    
#s=sorted(s,reverse=True,key= lambda x:x[2])

dp=[[-1 for h in range(H+1)]for i in range(N)]

for i in range(1,H+1):
    dp[0][i]=int(np.ceil(i/s[0][0]))*s[0][1]
dp[0][0]=0
print(search(N-1,H))

Submission status: Runtime Error

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

def mp(i, x):
    if x <= 0:
        return 0
    elif i == 1:
        return (x//ablis[0][1]+1)*ablis[0][2]
    else:
        return min(mp(i-1, x), mp(i, x-ablis[i-1][1])+ablis[i-1][2])

print(mp(n, h))

Submission status: Runtime Error

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

def mp(i, x):
    if x <= 0:
        return 0
    elif i == 0:
        return (x//ablis[0][1]+1)*ablis[0][2]
    else:
        return min(mp(i-1, x), mp(i, x-ablis[i-1][1])+ablis[i-1][2])

print(mp(n, h))

Submission status: Runtime Error

Solution code:
import sys
import math
from pprint import pprint
from collections import namedtuple


INF = sys.maxsize

Magic = namedtuple('Magic', 'damage cost')

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

magic = []

for _ in range(N):
  a, b = map(int, input().split())
  magic.append(Magic(a, b))

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

for i in range(N):
  for damage in range(0, H + 1):
    if damage == 0:
      memo[i][damage] = 0
      continue
    m = magic[i]
    #  1行目初期化
    if i == 0:
      memo[0][damage] = math.ceil(damage / m.damage) * m.cost
    else:
      memo[i][damage] = min(
        memo[i - 1][damage],
        memo[i][damage - m.damage] + m.cost
      )
            
print(memo[N - 1][H])

Submission status: Runtime Error

Solution code:
import sys

lines = sys.stdin.readlines()

H, M = list(map(int, lines[0].split()))
AB = []

max_at = 0
min_mg = sys.maxsize
at_min_mg = 0
for i in range(M):
  t = tuple(map(int, lines[i+1].split()))
  AB.append(t)
  if t[0]>=max_at:
    max_at = t[0]
  if t[1]<=min_mg:
    min_mg = t[1]
    at_min_mg = t[0]

ABlen = len(AB)

DP = [0]
for i in range(1, at_min_mg+1):
  DP.append(min_mg)
  
for i in range(at_min_mg+1,H+max_at):
  mm = 99999999
  for j in range(ABlen):
    if i-AB[j][0]<0:
      continue
    if mm > DP[i-AB[j][0]]+AB[j][1]:
      mm = DP[i-AB[j][0]]+AB[j][1]
  DP.append(mm)
print(min(DP[H:H+max_at-1]))

Submission status: Runtime Error

Solution code:
import sys

lines = sys.stdin.readlines()

H, M = list(map(int, lines[0].split()))
AB = []

max_at = 0
min_mg = 999999
at_min_mg = 0
for i in range(M):
  t = tuple(map(int, lines[i+1].split()))
  AB.append(t)
  if t[0]>max_at:
    max_at = t[0]
  if t[1]<min_mg:
    min_mg = t[1]
    at_min_mg = t[0]

ABlen = len(AB)

DP = [0]
for i in range(1, at_min_mg+1):
  DP.append(min_mg)
  
for i in range(at_min_mg+1,H+max_at):
  mm = sys.maxsize
  for j in range(ABlen):
    if i-AB[j][0]<0:
      continue
    if mm > DP[i-AB[j][0]]+AB[j][1]:
      mm = DP[i-AB[j][0]]+AB[j][1]
  DP.append(mm)
print(min(DP[H:H+max_at-1]))

Submission status: Runtime Error

Solution code:
import sys

lines = sys.stdin.readlines()

H, M = list(map(int, lines[0].split()))
AB = []

max_at = 0
min_mg = 999999
at_min_mg = 0
for i in range(M):
  t = tuple(map(int, lines[i+1].split()))
  AB.append(t)
  if t[0]>max_at:
    max_at = t[0]
  if t[1]<min_mg:
    min_mg = t[1]
    at_min_mg = t[0]

ABlen = len(AB)

DP = [0]
for i in range(1, at_min_mg+1):
  DP.append(min_mg)
  
for i in range(at_min_mg+1,H+max_at):
  mm = 99999999
  for j in range(ABlen):
    if i-AB[j][0]<0:
      continue
    if mm > DP[i-AB[j][0]]+AB[j][1]:
      mm = DP[i-AB[j][0]]+AB[j][1]
  DP.append(mm)
print(min(DP[H:H+max_at-1]))

Submission status: Runtime Error

Solution code:
import sys

lines = sys.stdin.readlines()

H, M = list(map(int, lines[0].split()))
AB = []

max_at = 0
min_mg = 999999
at_min_mg = 0
for i in range(M):
  t = tuple(map(int, lines[i+1].split()))
  AB.append(t)
  if t[0]>max_at:
    max_at = t[0]
  if t[1]<min_mg:
    min_mg = t[1]
    at_min_mg = t[0]

ABlen = len(AB)

DP = [0]
for i in range(1, at_min_mg+1):
  DP.append(min_mg)
  
for i in range(at_min_mg+1,H+max_at):
  mm = 999999
  for j in range(ABlen):
    if i-AB[j][0]<0:
      continue
    if mm > DP[i-AB[j][0]]+AB[j][1]:
      mm = DP[i-AB[j][0]]+AB[j][1]
  DP.append(mm)
print(min(DP[H:H+max_at-1]))

Submission status: Runtime Error

Solution code:
import sys

lines = sys.stdin.readlines()

H, M = list(map(int, lines[0].split()))
AB = []

max_at = 0
min_mg = 999999
at_min_mg = 0
for i in range(M):
  t = tuple(map(int, lines[i+1].split()))
  AB.append(t)
  if t[0]>max_at:
    max_at = t[0]
  if t[1]>min_mg:
    min_mg = t[1]
    at_min_mg = t[0]

ABlen = len(AB)

DP = [0]
for i in range(1, at_min_mg+1):
  DP.append(min_mg)
  
for i in range(at_min_mg+1,H+max_at):
  mm = 999999
  for j in range(ABlen):
    if i-AB[j][0]<0:
      continue
    if mm > DP[i-AB[j][0]]+AB[j][1]:
      mm = DP[i-AB[j][0]]+AB[j][1]
  DP.append(mm)
print(min(DP[H:H+max_at-1]))

Submission status: Runtime Error

Solution code:
import numpy as np
H,N = map(int, input().split())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
    
dp = [10**8+1 for i in range(H*N+1)]
dp[0] = 0
for i in range(H+1):
    for j in range(N):
        dp[i+A[j]] = min(dp[i+A[j]],dp[i]+B[j])
        
print(min(dp[H:]))

Submission status: Runtime Error

Solution code:
H,N = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
x = max(A)
dp = [10**9 for i in range(H+x+1)]
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(H+x+1):
        if j < a:
            continue
        dp[j] = min(dp[j-a]+b,dp[j])
ans = 10**9
for i in range(H,H+X+1):
    ans = min(ans,dp[i])
print(ans)

Submission status: Runtime Error

Solution code:
H,N = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
h = 2*10**4
dp = [10**9 for i in range(x+1)]
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(x+1):
        if j < a:
            continue
        dp[j] = min(dp[j-a]+b,dp[j])
ans = 10**9
for i in range(H,x+1):
    ans = min(ans,dp[i])
print(ans)

Submission status: Runtime Error

Solution code:
from numba import jit
import time
import numpy as np
t = time.time()
INF = 1 << 60


@jit
def Nap(h, n, ab, dp):

    for i in range(1, h + 10001):
        val = INF
        for j in range(n):
            if (i >= ab[j][0]):
                val = min(val, dp[i-ab[j][0]] + ab[j][1])
        dp[i] = min(val, dp[i])

    res = INF
    for i in range(h, h+10001):
        res = min(res, dp[i])
    return res


def pri(t):
    print("elapsed time:{:.2f}".format(time.time()-t))


def main():
    h, n = map(int, input().split())
    #ab = [[0, 0] for _ in range(n)]
    ab = np.zeros((n, 2), dtype=int)
    for i in range(n):
        a, b = map(int, input().split())
        ab[i][0] = a
        ab[i][1] = b

    #dp = [INF for _ in range(h+10001)]
    dp = np.full(h+10001, INF, dtype=int)

    dp[0] = 0
    print(Nap(h, n, ab, dp))
    # pri(t)


main()

Submission status: Runtime Error

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

INF = 100000000000
DP_list = [INF]*(H+20001)
def DP(h):
    ans = INF
    if h <= 0:
        return 0
    elif DP_list[h] != INF:
        return DP_list[h]
    else:
        for i in range(N):
            k = magic[i][1] + DP(h - magic[i][0])
            ans = min(ans,k)
        DP_list[h] = ans
        return ans

print(DP(H))

Submission status: Runtime Error

Solution code:
H,N=map(int,input().split())
p=[[]]
for i in range(N):
  x=list(map(int,input().split()))
  p.append(x)
#DPテーブル作成dp[i][j]=モンスターの体力j,i番目までの魔法を使った時の最小消費魔力
DP=[[0 for z in range(H+1)] for w in range(N+1)]
for j in range(H+1):
  q=j//p[1][0]+min(j%p[1][0],1)
  DP[1][j]=q*p[1][1]
for j in range(H+1):
  for i in range(1,N):
    S=10**8+1
    for k in range(j//p[i+1][0]+min(j%p[i+1][0],1)+1):
      T=k*p[i+1][1]+DP[i][j-k*p[i+1][0]]
      if S>T:
        S=T
    DP[i+1][j]=S
print(DP[N][H])

Submission status: Runtime Error

Solution code:
import sys


def solve(h, n, ab):
    ab.sort(key=lambda x: x[1] / x[0])
    INF = 10 ** 18
    cache = {}
    # とりあえず一番コスパいいやつだけを使った結果を暫定最良値としておく
    best = ((h - 1) // ab[0][0] + 1) * ab[0][1]

    def dp(k, i=0, cost=0):
        nonlocal best
        if k <= 0:
            return cost
        if (k, i) in cache:
            return cache[k, i] + cost
        a, b = ab[i]
        if k / a * b + cost >= best:
            # どう足掻いても残りでbestより良い結果は得られない
            return INF
        c = (k - 1) // a + 1
        if i == n - 1:
            ret = cost + b * c
        else:
            ret = min(dp(k - a * j, i + 1, cost + b * j) for j in range(c + 1))
        cache[k, i] = ret - cost
        best = min(best, ret)
        return ret

    dp(h)
    return best


sys.setrecursionlimit(1001)

h, n = map(int, input().split())
ab = [tuple(map(int, line.split())) for line in sys.stdin]
print(solve(h, n, ab))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(2000)
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)

memo = [10**4+1 for i in range(H+1)]

def memorize(H,memo,A,B,N):
    if H<= 0:
        return 0
    else:
        if memo[H]!=10**4+1:
            return memo[H]
        cost_min = 10**4+1
        for i in range(N):
            cost = B[i] + memorize(H-A[i],memo,A,B,N)
            cost_min = min(cost_min,cost)
        memo[H] = cost_min
        return cost_min
        
print(memorize(H,memo,A,B,N))

Submission status: Runtime Error

Solution code:
import numpy as np
sys.setrecursionlimit(10**4+1)
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)

memo = [10**4+1 for i in range(H+1)]

def memorize(H,memo,A,B,N):
    if H<= 0:
        return 0
    else:
        if memo[H]!=10**4+1:
            return memo[H]
        cost_min = 10**4+1
        for i in range(N):
            cost = B[i] + memorize(H-A[i],memo,A,B,N)
            cost_min = min(cost_min,cost)
        memo[H] = cost_min
        return cost_min
        
print(memorize(H,memo,A,B,N))

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())
magic = []
max_damage = 0
for i in range(n):
    magic.append(list(map(int, input().split())))
    max_damage = max(max_damage, magic[i][0])

# 一次元で可能
dp = [10**10 for _ in range(h+max_damage)]
dp[0] = 0

for damage, cost in magic:
    for j in range(h+max_damage):
        dp[j] = min(dp[j], dp[j-damage]+cost)

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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)
dp = [[float("inf")]*(h+3) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
    for j in range(h+3):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-a[i]]+b[i])
ans = float("inf")
for i in range(h,h+3):
    ans = min(ans,dp[n][i])

print(ans)

Submission status: Runtime Error

Solution code:
import sys

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

dp = [0 for _ in range(H+1)]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])

Submission status: Runtime Error

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


def main():
    h, n = map(int, input().split())
    # A = []
    # B = []
    # for _ in range(n):
    #     A.append(a)
    #     B.append(b)
        
    m = 2 * 10**4 + 10
    dp = [0] * (h+1)
    dp[0] = 0
    # for a, b in zip(A, B):
    #     dp[a] = b
    for i in range(h):
        a, b = map(int, input().split())
        # for a, b in zip(A, B):
        if i + a < m and dp[i] > 0:
            j = min(i+a, h)
            if dp[j] > 0:
                dp[j] = min(dp[j], dp[i] + b)
            else:
                dp[j] = dp[i] + b
    k = h
    # print(dp[:20])
    # while (flag):
    #     if dp[k] > 0:
    #         ans = dp[k]
    #         flag = 0
    #     k += 1
    # d = np.array(dp[k:])
    # print(np.min(d[d.nonzero()]))
    print(dp[h])
    
    
main()

Submission status: Runtime Error

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


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)
        
    m = 2 * 10**4 + 10
    dp = [0] * (h+1)
    for a, b in zip(A, B):
        dp[a] = b
        for i in range(h):
            for a, b in zip(A, B):
                if i + a < m and dp[i] > 0:
                    j = min(i+a, h)
                    if dp[j] > 0:
                        dp[j] = min(dp[j], dp[i] + b)
                    else:
                        dp[j] = dp[i] + b
    k = h
    # print(dp[:20])
    # while (flag):
    #     if dp[k] > 0:
    #         ans = dp[k]
    #         flag = 0
    #     k += 1
    # d = np.array(dp[k:])
    # print(np.min(d[d.nonzero()]))
    print(dp[h])
    
    
main()

Submission status: Runtime Error

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


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)
        
        m = 2 * 10**4 + 10
        dp = [10**5] * (h+1)
        for a, b in zip(A, B):
            dp[a] = b
            for i in range(h):
                for a, b in zip(A, B):
                    if i + a < m and dp[i] > 0:
                        j = min(i+a, h)
                        if dp[j] > 0:
                            dp[j] = min(dp[j], dp[i] + b)
                        else:
                            dp[j] = dp[i] + b
    k = h
    # print(dp[:20])
    # while (flag):
    #     if dp[k] > 0:
    #         ans = dp[k]
    #         flag = 0
    #     k += 1
    # d = np.array(dp[k:])
    # print(np.min(d[d.nonzero()]))
    print(dp[h])
    
    
main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readlin
INF = float('INF')


def main():
    H, N = map(int, input().split())
    skills = [None] * N
    max_a = 0
    for i in range(N):
        a, b = map(int, input().split())
        if a > max_a:
            max_a = a
        skills[i] = (a, b)

    # dpの配列準備
    # インデックス→体力、中身→その体力を削るための最小MP
    dp = [INF] * (H + max_a + 1111
    dp[0]=0


    # 各体力を削る最小MPをDPで更新していく
    for i in range(H):
        # そのHPをちょうど削る攻撃がない場合はそれ以降の行動を計算できないので飛ばす1
        if dp[i] == INF:
            continue

        # そうでない場合は、次の攻撃をシミュレーション
        for a, b in skills:
            # 攻撃した場合の累計消費MPを算出
            mp=dp[i] + b
            # その攻撃をした場合に削れる体力に割り当てられている消費MPと比較
            # より少ない消費MPで削れることがわかった場合は更新
            if mp < dp[i + a]:
                dp[i + a]=mp

    # 更新が終わったので、倒せるダメージのうち、累計消費MPが一番少ないものを出力
    print(min(dp[H:]))


 if __name__ == "__main__":
     main()

Submission status: Runtime Error

Solution code:
import numpy as np
import pandas as pd
import math
H,N = (int(x) for x in input().split())
A = np.array([0]*N)
B = np.array([0]*N)
C = np.array([0.]*N)
for i in range(N):
    A[i],B[i] = (int(x) for x in input().split())
    C[i] = float(A[i]) / float(B[i])

indexs = np.argsort(-C)
A=A[indexs]
B=B[indexs]
C=C[indexs]

V=[[0]*(H+1) for i in range(N+1)]
for h in range(H+1):
    V[0][h] = B[0]*math.ceil(h/A[0])

for i  in range(N):
    for h in range(H+1):
        if h < A[i]:
            V[i+1][h] = V[i][h]
        elif V[i][h] > (V[i][h-A[i]]+B[i]):
            V[i+1][h] = (V[i][h-A[i]]+B[i])
        else:
            V[i+1][h] = V[i][h]

print(V[N][H])

Submission status: Runtime Error

Solution code:
 import numpy as np
import pandas as pd
import math
H,N = (int(x) for x in input().split())
A = np.array([0]*N)
B = np.array([0]*N)
C = np.array([0.]*N)
for i in range(N):
    A[i],B[i] = (int(x) for x in input().split())
    C[i] = float(A[i]) / float(B[i])

indexs = np.argsort(-C)
A=A[indexs]
B=B[indexs]
C=C[indexs]

V=[[0]*(H+1) for i in range(N+1)]
for h in range(H+1):
    V[0][h] = B[0]*math.ceil(h/A[0])

for i  in range(N):
    for h in range(H+1):
        if h < A[i]:
            V[i+1][h] = V[i][h]
        elif V[i][h] > (V[i][h-A[i]]+B[i]):
            V[i+1][h] = (V[i][h-A[i]]+B[i])
        else:
            V[i+1][h] = V[i][h]

print(V[N][H])

Submission status: Runtime Error

Solution code:
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
        return bi


    print(calc(H))



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
H,N = map(int,input().split())
a = 10**5
for i in range(N):
b,c = map(int,input().split())
  if b/c <a:
    a = b/c
    d = H/b*c
print(d)

Submission status: Runtime Error

Solution code:
import numpy as np
import math

def solve_dp(arr, hp):
  dp_arr = np.full(hp+arr[-1][0], np.inf)
  for (attack, damage) in arr:
    dp_arr[attack] = damage

  for index, cost in enumerate(dp_arr[:hp]):
    if cost == np.inf or cost == math.inf:
      continue
    for attack, damage in arr:
      dp_arr[index+attack] = min(dp_arr[index+attack], cost+damage)
  return dp_arr


if __name__ == "__main__":
  _h, _n = map(int, input().split())
  toki_list = [tuple(map(int, input().split())) for i in range(_n)]
  toki_list = sorted(toki_list, key=lambda x:x[0])

  arr = solve_dp(toki_list, _h)
  ans = np.min(arr[_h:_h+toki_list[-1][0]])
  print(int(ans))

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())
dp = [10 ** 9] * (h+1)
dp[0] = 0

for ni in range(n):
  a, b = map(int, input().split())
  for hi 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:
import numpy as np
import sys
input = sys.stdin.readline


max_size = 10**4 + 2 * 10**3
h, n = map(int, input().split())
DP = np.ones(max_size, dtype=np.int64) * 10**9
DP[0] = 0

for _ in range(n):
    power, cost = map(int, input().split())
    for i in range((h+power-1)//power):
        np.minimum(DP[(i+1)*power: (i+2)*power], DP[(i)*power: (i+1)*power] + cost, DP[(i+1)*power: (i+2)*power])

print(DP[h:].min())