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:
H,N =map(int, input().split())
a = [] 
M = 0 
for i in range(N):
	t = list(map(int, input().split()))
	a.append(t)
	M = max(M,t[0])
dp = [10000]*(H+1)
dp[0] = 0
for i in range(1,H+M):
	for j,k in a:
		dp[i+j] = min(dp[i+j],dp[i]+k)

print(min(dp[H:]))

Submission status: Runtime Error

Solution code:
H ,N = [int(i) for i in input().split()]
AB = []
for _ in range(N):
    AB.append([int(i) for i in input().split(' ')])
 
MAX = 0
for a, b in AB:
    MAX = a if MAX < a else MAX
 
DP = [10**10] * (H+MAX)
DP[0] = 0
for i in range(H):
    for a,b in AB:
        if DP[i] != 10**10:
            DP[i+a] = min(DP[i+a],DP[i] + b)
 
print(min(DP[H:]))
H ,N = [int(i) for i in input().split()]
AB = []
for _ in range(N):
    AB.append([int(i) for i in input().split(' ')])

MAX = 0
for a, b in AB:
    MAX = a if MAX < a else MAX

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

print(min(DP[H:]))
提出情報

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
dp = [[100000000]*(10000*2)]*(N+1)
dp[0][0] = 0

for i in range(0, N):
    for h in range(0, H+1):
        dp[i+1][h] = min(dp[i+1][h], dp[i][h])
        dp[i+1][min(h+AB[i][0], H)] = min(dp[i+1][min(h+AB[i][0], H)], dp[i+1][h]+AB[i][1])

ans = {}
for i in range(N):
    ans[i] = dp[i][H]
print(min(ans.values()))

Submission status: Runtime Error

Solution code:
from sys import stdin
from sys import  setrecursionlimit
setrecursionlimit(3000)

[H, N] = [int(x) for x in stdin.readline().rstrip().split()]
As = []
Bs=[]
for i in range(N):
    [A, B] = [int(x) for x in stdin.readline().rstrip().split()]
    As.append(A)
    Bs.append(B)

#dp_map = []
#for i in range(N+1):
#    temp_arr = [-1 for _ in range(H+1)]
#    dp_map.append(temp_arr)
dp_map = [[-1]*(H+1) for _ in range(N+1)]
#dp_map = [[-1]*(H+1)]*(N+1)
#print(len(dp_map))
#print(len(dp_map[0]))

def DP(i, j):
    if j<=0:
        return 0
    if dp_map[i][j]!=-1:
        return dp_map[i][j]
    
    if i==1:
        dp_map[i][j] = DP(i,j-As[i-1])+Bs[i-1]
        return dp_map[i][j]

    dp_map[i][j] = min(DP(i-1,j),DP(i,j-As[i-1])+Bs[i-1])
    return dp_map[i][j]

print(DP(N,H))

Submission status: Runtime Error

Solution code:
from sys import stdin

[H, N] = [int(x) for x in stdin.readline().rstrip().split()]
As = []
Bs=[]
for i in range(N):
    [A, B] = [int(x) for x in stdin.readline().rstrip().split()]
    As.append(A)
    Bs.append(B)

dp_map = []
for i in range(N+1):
    temp_arr = [False for _ in range(H+1)]
    dp_map.append(temp_arr)

def DP(i, j):
    if j<=0:
        return 0
    if dp_map[i][j]!=False:
        return dp_map[i][j]
    
    if i==1:
        dp_map[i][j] = DP(i,j-As[i-1])+Bs[i-1]
        return dp_map[i][j]

    dp_map[i][j] = min(DP(i-1,j),DP(i,j-As[i-1])+Bs[i-1])
    return dp_map[i][j]

print(DP(N,H))

Submission status: Runtime Error

Solution code:
INF = float('inf')

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


# i個目までを使って与えた魔力の総和がj以下の時の最小コスト
dp = [[INF for j in range(H + 2)] for i in range(N + 1)]

dp[0][0] = 0

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

if dp[N][H] == INF:
    print(dp[N][H + 1])
else:
    print(dp[N][H])

Submission status: Runtime Error

Solution code:
INF = float('inf')

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


# i個目までを使って与えた魔力の総和がj以下の時の最小コスト
dp = [[INF for j in range(H + 1)] for i in range(N + 1)]

dp[0][0] = 0

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

if dp[N][H] == INF:
    print(dp[N][H + 1])
else:
    print(dp[N][H])

Submission status: Runtime Error

Solution code:
INF = float('inf')

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


# i個目までを使って与えた魔力の総和がj以下の時の最小コスト
dp = [[INF for j in range(H + 1)] for i in range(N + 1)]

dp[0][0] = 0

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

print(dp[N][H])

Submission status: Runtime Error

Solution code:
INF = 10**9

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


# i個目までを使って与えた魔力の総和がj以下の時の最小コスト
dp = [[0 for j in range(H + 1)] for i in range(N + 1)]

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

print(dp[H][N])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
H,N = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
mem = [0] * H
def dp(rem):
    global mem
    if mem[rem-1]:
        return mem[rem-1]
    elif rem <= 0:
        return 0
    else:
        a = min([dp(rem-AB[i][0]) + AB[i][1] for i in range(N)])
        mem[rem-1] = a
        return a
print(dp(H))

Submission status: Runtime Error

Solution code:
import math
h,n=map(int,input().split())
magica=[]
MP=0
for i in range(n):
  a,b=map(int,input().split())
  c=b/a
  c=math.floor(c*1000)/1000
  magica.append([c,a,b])
magic=sorted(magica)
def cast(h,i):
  if h % magic[i][1]==0:
    return (h//magic[i][1])*magic[i][2]
  elif i==n-1:
    return (h//magic[i][1] + 1)*magic[i][2]
  num=h//magic[i][1]
  return min((num+1)*magic[i][2],num*magic[i][2]+cast(h % magic[i][1],i+1))
MP=cast(h,0)
print(MP)

Submission status: Runtime Error

Solution code:
H,N=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(N)]
x=max(a for a,b in ab)
dp=[0]*(H+10)
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())
ab=[list(map(int,input().split())) for _ in range(N)]
dp=[0]*(H+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())
ab=[list(map(int,input().split())) for _ in range(N)]
dp=[0]*(H)
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())
AB=[]
for _ in range(N):
    a,b=map(int,input().split())
    AB.append((a,b))
dp=[0]*(H+1)
for i in range(1,H+1):
    for a,b in AB:
        if dp[i]==0:
            dp[i]=dp[max(i-a,0)]+b
        else:
            dp[i]=min(dp[i],dp[i-a]+b)
print(dp[H])

Submission status: Runtime Error

Solution code:
H,N=map(int,input().split())
AB=[]
for _ in range(N):
    a,b=map(int,input().split())
    AB.append((a,b))
AB.sort()
amax=AB[-1][0]
dp=[0]*(H+1)
for i in range(1,H+1):
    for a,b in AB:
        if dp[i]==0:
            dp[i]=dp[max(i-a,0)]+b
        else:
            dp[i]=min(dp[i],dp[i-a]+b)
print(dp[H])

Submission status: Runtime Error

Solution code:
H, N = map(int,input().split())
M = [list(map(int,input().split())) for k in range(N)]
dp = [float("inf")]*(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])

Submission status: Runtime Error

Solution code:
def main():
  H, N = (int(_) for _ in input().split())
  A = [[int(_) for _ in input().split()] for __ in range(N)]
  INF = 10 ** 15
  dp = [[INF] * (H + 1) for _ in range(N+1)]
  dp[0][0] = 0
  for i in range(N):
    for j in range(H+1):
      dp[i+1][j] = min(dp[i+1][j], dp[i][j])
      if A[i][0] <= j < H:
        dp[i+1][j] = min(dp[i+1][j], A[i][1] + dp[i+1][j-A[i][0]])
      elif j == H:
        for k in range(j - A[i][0], j):
          dp[i+1][j] = min(dp[i+1][j], A[i][1] + dp[i+1][k])
  print(dp[N][H])
  return

if __name__ == '__main__':
  main()

Submission status: Runtime Error

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

INF = 10**18
dp = [INF]*(h+1)
#dp[i]: hpがiの相手に消費する魔力の最小値
dp[0]=0

for i in range(h):#i:累積ダメージi
    for j in range(n):#
        if i+A[j]<=h: #
            dp[i+A[j]]=min(dp[i+A[j]],dp[i]+B[j])
        else:
            dp[-1]=min(dp[-1],dp[i]+B[j])
print(dp[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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))
magic.sort(reverse=True)

INF = 1<<60

def solve():
    btab = [INF] * (H+1)
    btab[0] = 0
    for h in range(1, magic[0][0]+1):
        btab[h] = min([b for a, b in magic if a >= h])
    for h in range(2, H+1):
        for a, b in magic:
            c = b + btab[max(h-a,0)]
            if c < btab[h]:
                btab[h] = c
    return btab[H]

print(solve())

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))
magic.sort(reverse=True)

INF = 1<<60

def solve():
    btab = [INF] * (H+1)
    btab[0] = 0
    for h in range(1, magic[0][0]+1):
        btab[h] = min([b for a, b in magic if a >= h])
    for h in range(2, H+1):
        for s in range(1, magic[0][0]+1):
            c = btab[s] + btab[h-s]
            if c < btab[h]:
                btab[h] = c
    return btab[H]

print(solve())

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))
magic.sort(reverse=True)

INF = 1<<60

def solve():
    btab = [INF] * (H+1)
    btab[0] = 0
    for h in range(1, magic[0][0]+1):
        btab[h] = min([b for a, b in magic if a >= h])
    for h in range(1, H+1):
        cand = [btab[s] + btab[h-s] for s in range(1, h) if s <= h-s]
        if not cand:
            continue
        cost = min(cand)
        if cost < btab[h]:
            btab[h] = cost
    return btab[H]

print(solve())

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from sys import stdin

[H, N] = [int(x) for x in stdin.readline().rstrip().split()]
As = []
Bs = []

for i in range(N):
    [a, b] = [int(x) for x in stdin.readline().rstrip().split()]
    As.append(a)
    Bs.append(b)


map_list = []
for i in range(10001):
    map_list.append(-1)


def DP(h):
    if h<=0:
        return 0
    if map_list[h]>=0:
        return map_list[h]
    
    temp_array = []
    for i in range(N):
        temp_array.append(DP(h-As[i])+Bs[i])
    map_list[h] = min(temp_array)
    

    return map_list[h]

print(DP(H))

Submission status: Runtime Error

Solution code:
#E再変更
#上から必要なものを順に呼び出していく一度使ったものは再利用
import sys
import resource

sys.setrecursionlimit(2*(10**4))

#入力
H,N=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]#[攻撃,魔力]
#処理
X=[-1 for i in range(H+1)]#計算していないものについては　-1を代入。
#それ以外にはその点での最小消費を代入
def E(h):#体力hの相手に対して最も最小の魔力消費
    if h<=0:
        return 0
    if X[h]>=0:#計算済み
        return X[h]
    else:#未計算
        #print(h,X)
        X[h]=min([E(h-M[i][0]) +M[i][1] for i in range(N)])
        return X[h]
        
print(E(H))

Submission status: Runtime Error

Solution code:
#E再変更
#上から必要なものを順に呼び出していく一度使ったものは再利用
import sys
import resource

sys.setrecursionlimit(20000)

#入力
H,N=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]#[攻撃,魔力]
#処理
X=[-1 for i in range(H+1)]#計算していないものについては　-1を代入。
#それ以外にはその点での最小消費を代入
def E(h):#体力hの相手に対して最も最小の魔力消費
    if h<=0:
        return 0
    if X[h]>=0:#計算済み
        return X[h]
    else:#未計算
        #print(h,X)
        X[h]=min([E(h-M[i][0]) +M[i][1] for i in range(N)])
        return X[h]
        
print(E(H))

Submission status: Runtime Error

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)


inf=float('inf')
component=[0]
for i in range(H):
    component.append(inf)
DP=[]
for j in range(N+1):
    DP.append(copy.copy(component))#DPは(N+1)×(H+1)


for k in range(1,N+1):#k番目の魔法
    for l in range(1,H+1):#体力H
        DP[k][l]=min(DP[k-1][l],DP[k][max(0,l-A[k-1])]+B[k-1])

print(DP[N][H])

Submission status: Runtime Error

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

dp = [float('inf')]*(h*2+1)
dp[0] = 0
for i in range(h):
    if dp[i] == float('inf'):
        continue
    for a, b in m:
        dp[i+a] = min(dp[i+a], dp[i]+b)
print(min(dp[h:]))

Submission status: Runtime Error

Solution code:
import math
h, n = map(int,input().split())
m = []
for i in range(n):
    a, b = map(int,input().split())
    m.append([a,b])
m.sort(reverse=True)

dp = [float('inf')]*(h*2+1)
dp[0] = 0
for i in range(h):
    for a, b in m:
        dp[i+a] = min(dp[i+a], dp[i]+b)

print(min(dp[h:]))

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)
A=np.array(A)
B=np.array(B)
#n番目を1回は使う時の魔力最小値
dp=np.zeros((H+1))
for i in range(1,H+1):
  dp[i]=(dp[i-A]+B).min()
  

      
      
print(int(dp[H]))

Submission status: Runtime Error

Solution code:
import math

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

dp=[[[float('INF'),0] for _ in range(H+1)]for i in range(N+1)]
dp[0]=[[0,0]for _ in range(H+1)]
for i in range(1,N+1):
  a = ab[i-1][0]
  b = ab[i-1][1]
  for j in range(1,H+1):
    limit = math.floor(j/a)+2
    for k in range(limit):
      mana = dp[i-1][j-(a*k)][0]+b*k
      damage = dp[i-1][j-(a*k)][1]+(a*k)
      if damage >= j:
        if dp[i][j][0] > mana:
          dp[i][j]=[mana,damage]
print(dp[N][H][0])

Submission status: Runtime Error

Solution code:
import math

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

dp=[[[float('INF'),0] for _ in range(H+1)]for i in range(N+1)]
dp[0]=[[0,0]for _ in range(H+1)]
for i in range(1,N+1):
  a = ab[i-1][0]
  b = ab[i-1][1]
  for j in range(1,H+1):
    limit = math.floor(j/a)+2
    for k in range(limit):
        mana = dp[i-1][j-(a*k)][0]+b*k
        damage = dp[i-1][j-(a*k)][1]+(a*k)
        if damage >= j:
            if dp[i][j][0] > mana:
                dp[i][j]=[mana,damage]
print(dp[N][H][0])

Submission status: Runtime Error

Solution code:
import math

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

dp=[[[float('INF'),0] for _ in range(H+1)]for i in range(N+1)]
dp[0]=[[0,0]for _ in range(H+1)]
for i in range(1,N+1):
  a = ab[i-1][0]
  b = ab[i-1][1]
  for j in range(1,H+1):
    limit = math.floor(j/a)+2
    for k in range(limit):
        mana = dp[i-1][j-(a*k)][0]+b*k
        damage = dp[i-1][j-(a*k)][1]+(a*k)
        if damage >= j:
            if dp[i][j][0] > mana:
                dp[i][j]=[mana,damage]

print(dp[N][H])

Submission status: Runtime Error

Solution code:
import math

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

dp=[[[float('INF'),0] for _ in range(H+1)]for i in range(N+1)]
dp[0]=[[0,0]for _ in range(H+1)]
for i in range(1,N+1):
  a = ab[i-1][0]
  b = ab[i-1][1]
  for j in range(1,H+1):
    limit = math.floor(j/a)+2
    for k in range(limit):
        mana = dp[i-1][j-(a*k)][0]+b*k
        damage = dp[i-1][j-(a*k)][1]+(a*k)
        if damage >= j:
            if dp[i][j][0] > mana:
                dp[i][j]=[mana,damage]
        

print(dp[N][H][0])

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())
magic = []
INF = 10 ** 9
for i in range(n):
    a, b = map(int, input().split())
    magic.append((a, b))
ans = 0
dp = [float('inf')] * (h + 1)

# 入力: 体力, 出力: 魔力の最小値
def magic_cost(hp):
    if dp[hp] != float('inf'):
        return dp[hp]

    cost_min = float('inf')
    for a, b in magic:
        if a >= hp:
            cost = b
        else:
            cost = b + magic_cost(hp - a)
        cost_min = min(cost, cost_min)
    dp[hp] = cost_min
    return cost_min

print(magic_cost(h))

Submission status: Runtime Error

Solution code:
H,N=[int(s) for s in input().split()]
ls=[[int(s) for s in input().split()] for _ in range(N)]
dp=[0 for _ in range(H+1)]
for i in range(1,H+1):
  s=set()
  for n in range(N):
    a,b=ls[n]
    s.add(dp[i-a]+b)
    dp[i]=min(s)
print(dp[H])

Submission status: Runtime Error

Solution code:
import numpy as np


def read():
    H, N = list(map(int, input().strip().split()))
    A = list()
    B = list()
    for i in range(N):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        B.append(b)
    return H, N, A, B


def solve(H, N, A, B, INF=10**9):
    BMAX = max(B)
    dp = np.empty(H + BMAX + 1, dtype=np.int32)
    dp[:] = INF
    dp[0] = 0
    for h in range(0, H + BMAX + 1, A[0]):
        dp[h] = dp[h-A[0]] + b[0]
    
    for h in range(0, H + BMAX + 1):
        for i in range(N):
            if h - A[i] >= 0:
                dp[h] = min(dp[h], dp[h - A[i] + B[i])
    return dp[H]


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Runtime Error

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


for i in range(h):
    for j in range(n):
        k=min(i+X[j][0],h)
        dp[k]=min(dp[k],dp[i]+X[j][1])
print(dp[h])

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+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:
def main():
    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])
      
if __name__ == '__main__':
    main()

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())
m=(h//a[0]+1)*b[0]
dp=[0]*(m+1)
dp2=[0]*(m+1)
for j in range(n):
    for i in range(b[j]+1):
        dp2[i]=dp[i]
    for i in range(b[j]+1,m+1):
        dp2[i]=max(dp2[i-b[j]]+a[j],dp[i])
        if(dp2[i]>=h):
            m=i
            break
    for i in range(m+1):
        dp[i]=dp2[i]
print(m-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())
m=(h//a[0]+1)*b[0]
dp=[0]*(m+1)
dp2=[0]*(m+1)
for j in range(n):
    for i in range(b[j]+1):
        dp2[i]=dp[i]
    for i in range(b[j]+1,m+1):
        dp2[i]=max(dp2[i-b[j]]+a[j],dp[i])
        if(dp2[i]>=h):
            m=i
            break
    for i in range(m+1):
        dp[i]=dp2[i]
    print(m)
print(m-1)

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A, B = ZIP(N)
A = np.array(A)
B = np.array(B)
max_A = A.max()

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

for i in range(1, H+1):
	dp[i]=(dp[i-A]+B).min()

print(dp[H])

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A, B = ZIP(N)
max_A = max(A)

L = H+max_A+1
dp = np.zeros(L, dtype=np.int64)
dp[1:] = 10**18
n = 1
for w, v in zip(B, A):
	dp[v:v+n] = np.minimum(dp[v:v+n], dp[:n]+w)
	n += v

print(dp[H:].min())

Submission status: Runtime Error

Solution code:
import math
import time

t = time.time()
def iip():
    return [int(i) for i in input().split()]

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

for i in range(N):
    a, b = iip()
    for j in range(H+1):
        if mp_for_damage[a] < b:
            continue

        for k in range(1, a):
            if k > H:
                break
            mp_for_damage[k] = min(mp_for_damage[k], b)

        if j + a > H:
            break
        mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

#print(mp_for_damage)
print(mp_for_damage[H])

#print(time.time() - t)

Submission status: Runtime Error

Solution code:
import math
import time

t = time.time()
def iip():
    return [int(i) for i in input().split()]

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

for i in range(N):
    a, b = iip()
    for j in range(H+1):
        for k in range(1, a):
            mp_for_damage[k] = min(mp_for_damage[k], b)

        if j + a > H:
            break
        mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

#print(mp_for_damage)
print(mp_for_damage[H])

#print(time.time() - t)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
readline = sys.stdin.readline
H, N = map(int, readline().split())
AB = [tuple(map(int, readline().split())) for _ in range(N)]

@lru_cache(maxsize=None)
def f(h):
    minb = -1
    for i in range(N):
        a, b = AB[i]
        if a < h:
            b += f(h - a)
        if minb < 0 or b < minb:
            minb = b
    return minb

ans = f(H)
print(ans)

Submission status: Runtime Error

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

#define REP(i,n) for(int i=0;i<n;i++)
#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


using namespace std;
using ll=long long;
ll mod = 1e9 + 7;

//int dp[1e5];
//memset(dp, BMAX*HMAX, sizeof(dp));
  
int main() {
    int H, N;
    cin >> H >> N;
    vector<int> A(N), B(N);
    for(int i=0;i<N;i++){
        cin >> A[i] >> B[i];
    }
    vector<ll> dp(H+1, 1e9);
    dp[0] = 0;
    for(int i=0;i<H;i++){
        for(int j=0;j<N;j++){
            chmin(dp[min(i+A[j], H)], dp[i]+B[j]);
        }
    }
    cout << dp[H] << endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
import math
mod = 10**9 + 7

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

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

dp = [math.inf] * (h+1)
dp[0] = 0

for i in range(n):

    for j in range(h):

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


print(dp[h])

Submission status: Runtime Error

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
mod = 10**9 + 7

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

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

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


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


print(dp[h])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define MAX 1e9
#define ll long long int
int main(){
  ll h,n;
  cin>>h>>n;
  ll a[n],b[n];
  
  for(ll i=0;i<n;i++) cin>>a[i]>>b[i];
  ll dp[h+1];
  for(ll i=0;i<=h;i++) dp[i]=MAX;
  dp[0]=0;
  for(ll i=0;i<=h;i++){
    for(ll j=0;j<n;j++)
      dp[i]=min(dp[max((ll)0,i-a[j])]+b[j],dp[i]);
  
  }
  cout<<dp[h];
}

Submission status: Runtime Error

Solution code:
#int でsplitを使う場合はmap関数を利用しなければならない
H,N = map(int,input().split())
li=[]
x=[]
for i in range(N):
    A,B = map(int,input().split())
    x.append(A)
    li.append([A,B])
dp = [10**9]*(H+max(x))
dp[0] = 0
for i in range(1,len(dp)):
    dp[i] = min(dp[i-a] + b for a,b in li)
print(min(dp[h:]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

a = ab[:, 0]
b = ab[:, 1]

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

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

print(dp[h])

Submission status: Runtime Error

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

for i in range(N):
    data.append([0, 0])
    a, b = map(int,input().split())
    data[i][0] = a
    data[i][1] = b
data.sort
cost = [float("inf")] * (H + data[-1][0])
cost[0] = 0
for i in range(1, H + data[-1][0]):
    for magic in data:
        if i < magic[0]:
            break
        if cost[i] > cost[i - magic[0]] + magic[1]:
            cost[i] = cost[i - magic[0]] + magic[1]
print(min(cost[H:]))
print(2/0)

Submission status: Runtime Error

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

a = ab[:, 0]
b = ab[:, 1]

dp = np.zeros(10**9, dtype=np.int)

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

print(dp[h])

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
H,N=map(int,input().split())
l=[1000000000]*(H+1)
l[0]=0
for i in range(N):
    A,B=map(int,input().split())
    for j in range(1,A+1):
        if l[j]>B:
            l[j]=B
    for j in range(H):
        if j+A<=H:
            if l[j]+B<l[j+A]:
                l[j+A]=l[j]+B
print(l[-1])

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A, B = [0]*N, [0]*N

for i in range(N):
	A[i], B[i] = MAP()

max_A = max(A)
dp = [INF]*(H+max_A+1)
dp[0] = 0
for i in range(N):
	for j in range(A[i], H+max_A+1):
		dp[j] = min(dp[j], dp[j-A[i]]+B[i])

print(min(dp[N][H:]))

Submission status: Runtime Error

Solution code:
INF = 1000000000

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

maxA = max(AB[:][0])

dp = [INF for i in range(h+maxA)]
dp[0] = 0

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

print(min(dp[h:]))

Submission status: Runtime Error

Solution code:
INF = 10000000

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

maxA = max(AB[:][0])

dp = [INF for i in range(h+maxA)]
dp[0] = 0

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

ans = min(dp[h:])

print(ans)

Submission status: Runtime Error

Solution code:
h, n, *L = map(int, open(0).read().split())
dp = [0] * (h + 1)
for i in range(1, h + 1):
    dp[i] = min(dp[i - a] + b for a, b in zip(*[iter(L)] * 2))

print(dp[h])