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: Time Limit Exceeded

Solution code:
import numpy as np
H,N=map(int,list(input().split(" ")))
magic=[]
power=[]
for i in range(N):
    A,B=map(int,list(input().split(" ")))
    magic+=[A]
    power+=[B]
dp=[[np.inf for i in range(H+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0]=0
ma=[]
for j in range(1,H+1):
    for i in range(1,N+1):
        if j-magic[i-1]>=0:
            dp[i][j]=min(dp[i-1][j],dp[i][j-magic[i-1]]+power[i-1])
        else:
            dp[i][j]=min(dp[i-1][j],power[i-1])
print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,N=map(int,list(input().split(" ")))
magic=[]
power=[]
for i in range(N):
    A,B=map(int,list(input().split(" ")))
    magic+=[A]
    power+=[B]
dp=[[np.inf for i in range(2*H+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0]=0
ma=[]
for j in range(1,2*H+1):
    for i in range(1,N+1):
        if j-magic[i-1]>=0:
            dp[i][j]=min(dp[i-1][j],dp[i][j-magic[i-1]]+power[i-1])
        else:
            dp[i][j]=min(dp[i-1][j],power[i-1])
print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
inf = 1000000000
dp = [inf] * 20000

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

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

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

print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

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

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
import math

h, n = map(int, input().split())
a = [0] * n
b = [0] * n
#print(a, b)
for i in range(n):
    a[i], b[i] = map(int, input().split())

#print(a)
#print(b)
INF = int(1e10)
dp = [[INF] * (h+1) for i in range(n+1)]
for i in range(h+1):
    dp[0][i] = math.ceil(i / a[0]) * b[0]
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    for j in range(h+1):
        if j < a[i]:
            dp[i+1][j] = min(math.ceil(j / a[i]) * b[i], dp[i][j])
        else:
            dp[i+1][j] = min(math.ceil(j/ a[i]) * b[i], dp[i][j], dp[i+1][j - a[i]] + b[i])
#print(dp)
print(dp[n][h])

Submission status: Time Limit Exceeded

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

a = []
b = []

for i in range(N):
  a_dash,b_dash = map(int,input().split())
  a.append(a_dash)
  b.append(b_dash)

#dp[i+1][j] = i番目までの魔法で体力jのモンスターに
#勝つことができる、魔力の最小値
INF = 10**9
dp = [[INF for _ in range(H+1)] for _ in range(N+1)]

#体力0のモンスターは初めからデスしている
for i in range(N+1):
  dp[i][0] = 0

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

print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
import sys

def dp_all(dp):
  length = len(dp)
  for i in range(length):
    print(dp[i])

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

a = []
b = []

for i in range(N):
  a_dash,b_dash = map(int,input().split())
  a.append(a_dash)
  b.append(b_dash)

#dp[i+1][j] = i番目までの魔法で体力jのモンスターに
#勝つことができる、魔力の最小値
INF = 10**9
dp = [[INF for _ in range(H+1)] for _ in range(N+1)]

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

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

print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
import sys

def dp_all(dp):
  length = len(dp)
  for i in range(length):
    print(dp[i])

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

a = []
b = []

for i in range(N):
  a_dash,b_dash = map(int,input().split())
  a.append(a_dash)
  b.append(b_dash)

#dp[i+1][j] = i番目までの魔法で体力jのモンスターに
#勝つことができる、魔力の最小値
INF = 10**9
dp = [[INF for _ in range(H+1)] for _ in range(N+1)]
#dp[0] = [0 for _ in range(H+1)]

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

print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
#E re
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 = [float('inf')] * (H+1)
DP[0] = 0

for i in range(N):
    for j in range(H):
        nj = min(j+A[i], H)
        DP[nj] = min(DP[nj], DP[j]+B[i])

print(int(DP[H]))

Submission status: Time Limit Exceeded

Solution code:
#E re
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] * H

for i in range(H):
    minM = float('inf')
    for j in range(N):
        if i+1 - A[j] >= 0:
            M = DP[i-A[j]] + B[j]
        else:
            M = B[j]
        if minM > M:
            minM = M
    DP[i] = minM

print(int(DP[H-1]))

Submission status: Time Limit Exceeded

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

INF = 10 ** 9
dp = [INF] * (h+1)
dp[h] = 0
for a, b in ab:
    for hi in range(h, 0, -1):
        if hi - a <= 0:
            dp[0] = min(dp[0], dp[hi]+b)
            #print('x', dp)
        else:
            dp[hi-a] = min(dp[hi-a], dp[hi]+b)
            #print(' ', dp)
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines

H,N=map(int,readline().split())
A=[0]*N
B=[0]*N
for i in range(N):
  A[i],B[i]=map(int,readline().split())

INF=10**9
dp=[INF]*(H+max(A))
# dp[x]:xダメージを与えるための最小魔力
dp[0]=0
for i in range(N):
  for j in range(H):
    if dp[j]!=INF:
      if dp[j+A[i]]>dp[j]+B[i]:
        dp[j+A[i]]=dp[j]+B[i]
print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
#配るDP
#AtCorder143
def dis_dp(N,H,a_list,b_list):
    #初期化
    inf = float("inf")
    dp = [[inf for i in range(H+1)] for b in range(N+1)]
    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: Time Limit Exceeded

Solution code:
#配るDP
#AtCorder143
def dis_dp(N,H,a_list,b_list):
    #初期化
    inf = float("inf")
    dp = [[inf for i in range(10**4)] for b in range(10**4)]
    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: Time Limit Exceeded

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

minpower = 10 ** 8 + 1

# dp[n][h] = 0 ~ n - 1 番目の魔法を使えた時、残り体力がhのモンスターを倒すために必要な魔力
dp = [[minpower for _ in range(H + 1)] for __ in range(N)]
for h in range(H):
    dp[0][h] = math.ceil(h / AB[0][0]) * AB[0][1]

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

for h in range(H + 1):
    for n in range(N):
        a, b = AB[n]

        if h - a < 0:
            dp[n][h] = min(
                dp[n-1][h],
                b
            )
        else:
            dp[n][h] = min(
                dp[n-1][h],
                dp[n][h-a] + b)
print(dp[-1][H])

Submission status: Time Limit Exceeded

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

minpower = 10 ** 10

# dp[n][h] = 0 ~ n - 1 番目の魔法を使えた時、残り体力がhのモンスターを倒すために必要な魔力
dp = [[minpower for _ in range(H + 1)] for __ in range(N)]
for h in range(H):
    dp[0][h] = math.ceil(h / AB[0][0]) * AB[0][1]

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

for h in range(H + 1):
    for n in range(N):
        a, b = AB[n]

        if h - a < 0:
            dp[n][h] = min(
                dp[n-1][h],
                b
            )
        else:
            dp[n][h] = min(
                dp[n-1][h],
                dp[n][h-a] + b)
print(dp[-1][H])

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, M = map(int, input().split())
    INF = 10 ** 9
    dp = [INF] * (10 ** 7)
    dp[0] = 0

    for _ in range(M):
        a, b = list(map(int, input().split()))
        for i in range(N + 1):
            if dp[i] == INF:
                continue
            dp[i+a] = min(dp[i+a], dp[i] + b)
    return min(dp[N:])

print(solve())

Submission status: Time Limit Exceeded

Solution code:
def solve():
    H, N = map(int, input().split())
    
    INF = 10 ** 9
    dp = [INF] * (10 ** 7)
    dp[0] = 0

    for _ in range(N): 
        a, b = list(map(int, input().split()))
        for i in range(H+1):
            if dp[i] == INF: continue
            dp[i+a] = min(dp[i+a], dp[i] + b)
            
    return min(dp[H:])

print(solve())

Submission status: Time Limit Exceeded

Solution code:
def solve():
    H, N = map(int, input().split())
    
    INF = 10 ** 9
    dp = [INF for _ in range(10 ** 7)]
    dp[0] = 0

    for _ in range(N): 
        a, b = list(map(int, input().split()))
        for i in range(H+1):
            if dp[i] == INF: continue
            dp[i+a] = min(dp[i+a], dp[i] + b)
            
    return min(dp[H:])

print(solve())

Submission status: Time Limit Exceeded

Solution code:
def solve():
    H, N = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    
    INF = 10 ** 9
    dp = [INF for _ in range(10 ** 7)]
    dp[0] = 0

    for a, b in A:
        for i in range(H+1):
            if dp[i] == INF: continue
            dp[i+a] = min(dp[i+a], dp[i] + b)
            
    return min(dp[H:])

print(solve())

Submission status: Time Limit Exceeded

Solution code:
INF = 10**15
hp, n_magic = map(int, input().split())
magic_data = tuple(tuple(map(int, input().split())) for _ in range(n_magic))
hp_gauge = [0] + [INF] * hp

for i in range(hp):
    for j in range(len(magic_data)):
        damage_total = i + magic_data[j][0]
        if damage_total > hp:
            damage_total = hp
        hp_gauge[damage_total] = min(hp_gauge[damage_total], hp_gauge[i] + magic_data[j][1])

print(hp_gauge[hp])

Submission status: Time Limit Exceeded

Solution code:
H,N=map(int,input().split())
A=[]
B=[]
for i in range(N):
  a,b=map(int,input().split())
  A+=[a]
  B+=[b]
dp=[[float('inf') for i in range(H+1)]for i in range(N+1)]#i番めの魔法までを使って体力j減らすのに必要な魔力の最小値
dp[0][0]=0
for i in range(1,N+1):
  for j in range(H+1):
    if j>=A[i-1]:
      Ai=A[i-1]
      Bi=B[i-1]
      dp[i][j]=min(dp[i][j-Ai]+Bi,dp[i-1][j])
    else:
      dp[i][j]=min(dp[i-1][j],B[i-1])
ans=dp[N][H]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
H,N = list(map(int, input().split()))
A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
# 1回iを使ってから、のこりをjで仕留める、を全探索でよい気がする
# だめだった

# dp[i] : HPをi減らすために必要なmin魔力
dp = [1e9] * (10010)
dp[0] = 0
for i in range(1,H+1):
  for a in A:
    ap, mp = a
    down = max(0, i - ap)
    dp[i] = min(dp[i], dp[down] + mp)
      
print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
H,N = list(map(int, input().split()))
A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
# 1回iを使ってから、のこりをjで仕留める、を全探索でよい気がする
# だめだった

# dp[i] : HPをi減らすために必要なmin魔力
dp = [1e9] * (10010)
dp[0] = 0
for i in range(1,H+1):
  for a in A:
    ap, mp = a
    down = max(0, i - ap)
    dp[i] = min(dp[i], min(dp[down:i]) + mp)
      
print(dp[H])

Submission status: Time Limit Exceeded

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

dp = [[10 ** 8 for _ in range(h + max(A) + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, h + max(A) + 1):
        if j <= A[i - 1]:
            dp[i][j] = min(dp[i - 1][j], B[i - 1])
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - A[i - 1]] + B[i - 1])

ans = min([dp[n][i] for i in range(h, h + max(A) + 1)])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Python3ではTLE
# PyPyなら回る
h, n = map(int, input().split())
inf = 1001001001
dp = [[inf for _ in range(h+1)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h + 1):
        # 外側参照しないように
        nj = max(0, j-a)
        dp[i+1][j] = min(dp[i][j], dp[i+1][nj]+b)

print(dp[n][h])

Submission status: Time Limit Exceeded

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

def main():
    H,N = map(int,input().split())
    x = []
    ma = 0
    for _ in range(N):
        a,b = map(int,input().split())
        ma = max(ma,a)
        x.append((a,b))
    INF = 10**10
    
    dp = [INF for _ in range(H+ma+1)]
    dp[0] = 0
    for a,b in x:
        for i in range(a,H+ma+1):
            if dp[i-a] != INF:
                dp[i] = min(dp[i],dp[i-a]+b)
    
    print(min(dp[H:]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(10001)

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: Time Limit Exceeded

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)

MY_INF = 10 ** 18

d = [MY_INF] * (H + 10000 + 1) # max(A) <= 10000

import heapq

q = [(0, 0)]
while len(q) > 0:
    pen, pos = heapq.heappop(q)
    if pos >= H: continue
    for i, (Ai, Bi) in enumerate(AB):
        pos_nxt = pos + Ai
        pen_nxt = pen + Bi
        if d[pos_nxt] > pen_nxt:
            d[pos_nxt] = pen_nxt
            heapq.heappush(q, (pen_nxt, pos_nxt))

ans = MY_INF
for i in range(H, H + 10000 + 1):
    ans = min(ans, d[i])

print(ans)

Submission status: Time Limit Exceeded

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)

MY_INF = 10 ** 18

d = [MY_INF] * (H + 10000 + 1) # max(A) <= 10000

import heapq

q = [(0, 0)]
while len(q) > 0:
    pos, pen = heapq.heappop(q)
    if pos >= H: continue
    for i, (Ai, Bi) in enumerate(AB):
        pos_nxt = pos + Ai
        pen_nxt = pen + Bi
        if d[pos_nxt] > pen_nxt:
            d[pos_nxt] = pen_nxt
            heapq.heappush(q, (pos_nxt, pen_nxt))

ans = MY_INF
for i in range(H, H + 10000 + 1):
    ans = min(ans, d[i])

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def chmin(a, b):
    if a > b:
        return b
    else:
        return a

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

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
#"""
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))
ma=[]
for _ in range(n):
    tmp=list(map(int,input().split()))
    ma.append(tmp)


#"""
#h=10**4
#n=10**3
#ma=[[i,i+1] for i in range(n)]

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


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

Submission status: Time Limit Exceeded

Solution code:
H, N= map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
ma = max(A)
dp = [0] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        if dp[j] == 0:
            dp[j] = dp[j - a] + b
        else:
            dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))

Submission status: Time Limit Exceeded

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

dp = [10**10] * (H+1)
dp[0] = 0
for i in range(1,H+1):
    for m in magic:
        if m[0] > i:
            dp[i] = min(dp[i], m[1])
        else:
            dp[i] = min(dp[i], dp[i-m[0]]+m[1])

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

dp = np.zeros((H+max(A), ))
# dp[i]: 体力をi減らすのに必要なcostの最小値

for  i in range(0, len(dp), 1):
    if i == 0:
        continue
    else:
        costs = []
        for a, b in zip(A, B):
            if i <= a:
                costs.append(b)
            else:
                cost = dp[i-a] + b
                costs.append(cost)
        dp[i] = min(costs)
        
print(int(min(dp[H:])))

Submission status: Time Limit Exceeded

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

dp = [int(1e8) for i in range(H+1)]
dp[0] = 0

for h in range(1,H+1):
  cand = [dp[0] + AB[n][1] if h - AB[n][0] < 0 else dp[h-AB[n][0]] + AB[n][1]for n in range(1,N+1) ]
  dp[h] = min(cand)
print(dp[H])

Submission status: Time Limit Exceeded

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

dp = [int(1e8) for i in range(H+1)]
dp[0] = 0

for h in range(1,H+1):
  cand = []
  for n in range(1,N+1):
    if h - AB[n][0] < 0:
        cand.append(dp[0] + AB[n][1])
    else:
        cand.append(dp[h-AB[n][0]] + AB[n][1])
  dp[h] = min(cand)
print(dp[H])

Submission status: Time Limit Exceeded

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

dp = [[int(1e8) for i in range(H+1)] for j in range(N+1)] 
for n in range(N+1):
  dp[n][0] = 0

for n in range(1,N+1):
  for h in range(1,H+1):
    ionly_n = int(h/AB[n][0]) + 1
    cand = [dp[n-1][h-i_n*AB[n][0]] + AB[n][1] * i_n for i_n in range(ionly_n)] + [AB[n][1] * ionly_n]
    dp[n][h] = min(cand)
#print(dp)
print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
H, N = [int(x) for x in input().split(' ')]
A = [0 for _ in range(N)]
B = A.copy()
for i in range(N):
  A[i], B[i] = [int(x) for x in input().split(' ')]
dp = [2100000000 for x in range(H+max(A)+1)]
dp[0] = 0
for i in range(N):
  a, b = A[i], B[i]
  dp[a] = min(dp[a], b)
  for j in range(a+1, H+a+1):
      dp[j] = min(dp[j], dp[j-a]+b)
print(min(dp[H:H+max(A)+1]))

Submission status: Time Limit Exceeded

Solution code:
H, N = [int(x) for x in input().split(' ')]
dp = [2100000000 for x in range(H+10001)]
dp[0] = 0
amax = 0
for i in range(N):
  A, B = [int(x) for x in input().split(' ')]
  amax = max(amax, A)
  dp[A] = min(dp[A], B)
  for j in range(A+1, H+A+1):
      dp[j] = min(dp[j], dp[j-A]+B)
print(min(dp[H:H+amax+1]))

Submission status: Time Limit Exceeded

Solution code:
MAX_A = 10000
INF = float('inf')
H, N = map(int, input().split(' '))
dp = [INF for x in range(H+MAX_A)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split(' '))
  dp[A] = min(dp[A], B)
  for j in range(A, H+A+1):
      dp[j] = min(dp[j], dp[j-A]+B)
print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
MAX_A = 10000
INF = float('inf')
H, N = map(int, input().split(' '))
dp = [INF for x in range(H+MAX_A)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split(' '))
  for j in range(1, H+MAX_A):
    if j == A:
      dp[j] = min(dp[j], B)
    elif j > A:
      dp[j] = min(dp[j], dp[j-A]+B)
print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
H, N = [int(i) for i in input().split(' ')]
dp = [INF for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  a, b = [int(x) for x in 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: Time Limit Exceeded

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

for i in range(n):
	for j in range(p+h):
		if j+1-ab[i][0]>=0:
			dp[i+1][j+1]=min(dp[i][j+1],dp[i+1][j+1-ab[i][0]]+ab[i][1])
		else:
			dp[i+1][j+1]=dp[i][j+1]
ans=10**10
for i in range(h,h+p):
	ans=min(dp[n][i],ans)
print(ans)

Submission status: Time Limit Exceeded

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

A = [0] * (N+1)
B = [0] * (N+1)
#magic = np.zeros((N+1, 2), dtype=int)

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

# print(magic)
# print(A)
# print(B)

INF = 100000010  # 10^4 * 10^4 + spare

#dp = np.full((N+1, H*2+1), INF)
#dp[0][0] = 0

dp = [INF]*(H+1)
#dp = np.full(H+1, INF, dtype=int)
dp[0] = 0

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

#        print(dp[i])
#    print(dp)

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

magic = np.zeros((N+1, 2), dtype=int)

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

# print(magic)

INF = 110000000  # 10^4 * 10^4 + spare

#dp = np.full((N+1, H*2+1), INF)
#dp[0][0] = 0

dp = np.full(H+1, INF, dtype=int)
dp[0] = 0

for i in range(1, N+1):
    for j in range(H + 1):
        # 貰うDP
        if j-magic[i][0] >= 0:
            dp[j] = min(dp[j - magic[i][0]] + magic[i][1], dp[j])
        else:
            dp[j] = min(dp[0] + magic[i][1], dp[j])

#        print(dp[i])
#    print(dp)

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int,input().split())
skills = []
for _ in range(n):
  a,b = map(int,input().split())
  skills.append((a,b))
dp = [float('inf') for _ in range(h+max(skills,key=lambda x:x[1])[1] + 1)]
dp[0] = 0
  
for i in range(len(dp)):
  if dp[i] ==float('inf'):
    continue
  for damage,mp in skills:
    if i+damage >= len(dp):
      continue
    if dp[i+damage] > dp[i] + mp:
      dp[i+damage] = dp[i]+mp
ans = min(filter(lambda x :x>0,dp[h:]))
print(ans)
#print(dp)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    h, n = map(int, input().split())
    w = []
    v = []
    for i in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[0 for i in range(h + 1)] for j in range(n + 1)]
    for i in range(1, h + 1):
        dp[0][i] = float("inf")
    for i in range(n):
        for j in range(h + 1):
            if j >= w[i]:
                dp[i + 1][j] = min(dp[i + 1][j - w[i]] + v[i], dp[i][j])
            else:
                dp[i + 1][j] = min(dp[i][j], v[i])
    print(dp[n][h])


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
l=[[0,0] for _ in range(n)]
#dp=[0 for _ in range(h+1)]
mnc=100000
for i in range(n):
  d,m=map(int,input().split())
  l[i]=[d,m]
  c=d/m
  mnc=min(c,mnc)
r=int(h/mnc)+2
mxdm=[0 for _ in range(r)] #mp=i+1のときの最大ダメージ
for i in range(1,r):
  for j in range(n):
    d,m=l[j][0],l[j][1]
    if i>=m:
      mxdm[i]=max(mxdm[i],mxdm[i-m]+d)
      #print(mxdm[i])
  if mxdm[i]>=h:
    print(i)
    exit()






print(mxdm)

Submission status: Time Limit Exceeded

Solution code:
x=input().split()
h=int(x[0])
n=int(x[1])
a=[]
b=[]
for k in range(n):
  x=input().split()
  a.append(int(x[0]))
  b.append(int(x[1]))  
m=max(a)  
dp=[10**8]*(h+m)
dp[0]=0
for k in range(h+m):
  temp=[]
  for i in range(n):
    if k-a[i]<0:
      continue
    if dp[k-a[i]]==10**8:
      continue
    temp.append(dp[k-a[i]]+b[i])
  if len(temp)>0:
    dp[k]=min(temp)
print(min(dp[h:h+m]))

Submission status: Time Limit Exceeded

Solution code:
x=input().split()
h=int(x[0])
n=int(x[1])
a=[]
b=[]
for k in range(n):
  x=input().split()
  a.append(int(x[0]))
  b.append(int(x[1]))  
m=max(a)  
dp=[10**8]*(h+m)
dp[0]=0
for k in range(h+m):
  for i in range(n):
    if k-a[i]<0:
      continue
    if dp[k-a[i]]==10**8:
      continue
    new=dp[k-a[i]]+b[i]
    if new < dp[k]:
      dp[k]=new
print(min(dp[h:h+m]))

Submission status: Time Limit Exceeded

Solution code:
x=input().split()
h=int(x[0])
n=int(x[1])
a=[]
b=[]
for k in range(n):
  x=input().split()
  a.append(int(x[0]))
  b.append(int(x[1]))  
m=max(a)  
import numpy as np 
dp=np.zeros(h+m)+10**8
dp[0]=0
for k in range(h+m):
  for i in range(n):
    if k-a[i]<0:
      continue
    new=dp[k-a[i]]+b[i]
    if new < dp[k]:
      dp[k]=new
print(int(np.min(dp[h:h+m])))

Submission status: Time Limit Exceeded

Solution code:
x=input().split()
h=int(x[0])
n=int(x[1])
a=[]
b=[]
for k in range(n):
  x=input().split()
  a.append(int(x[0]))
  b.append(int(x[1]))  
m=max(a)  
dp=[10**8]*(h+m)
dp[0]=0
for k in range(h+m):
  for i in range(n):
    if k-a[i]<0:
      continue
    new=dp[k-a[i]]+b[i]
    if new < dp[k]:
      dp[k]=new
print(min(dp[h:h+m]))

Submission status: Time Limit Exceeded

Solution code:
x=input().split()
h=int(x[0])
n=int(x[1])
a=[]
b=[]
for k in range(n):
  x=input().split()
  a.append(int(x[0]))
  b.append(int(x[1]))  
m=max(a)  
dp=[10**8]*(h+m)
dp[0]=0
for k in range(h+m):
  for i in range(n):
    if k-a[i]<0:
      continue
    new=dp[k-a[i]]+b[i]
    if new < dp[k]:
      dp[k]=new
print(min(dp[h:h+m]))

Submission status: Time Limit Exceeded

Solution code:
h,n = map(lambda x: int(x),input().split())
a,b = [],[]
f_inf = float('inf')

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

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


print(dp[h])

Submission status: Time Limit Exceeded

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

sab=sorted(ab)
maxl = 2*10**8
maxa=sab[len(sab)-1][0]
maxi = h+sab[len(sab)-1][0]
ans = [maxl]*maxi
ans[0] = 0

for i in range(1,maxi):
  for j in range(0,n):
    if i < sab[j][0]:
      break
    ans[i] = min(ans[i-sab[j][0]]+sab[j][1], ans[i])

#print(sab)
#print(ans)
print(min(ans[h:]))

Submission status: Time Limit Exceeded

Solution code:
hn = list(map(int, input().split()))
h = hn[0]
n = hn[1]

magic = []
max_attack = 0
for i in range(n):
    magic.append(list(map(int, input().split())))
    max_attack = max(max_attack, magic[-1][0])

f_inf = float('inf')

c = [f_inf] * (h+1+max_attack)
c[0] = 0

for m in magic:
    index = 0
    for i in range(1, h+1+max_attack):
        if i >= m[0]:
            c[i] = min(c[i-m[0]] + m[1], c[i])

cc = c[h:]
print(min(cc))