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 sys
sys.setrecursionlimit(10**9)

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

    tp = 3 * 10**4
    dp = [INF] * tp
    dp[0] = 0
    minim = INF
    for h in range(tp):
        for i in range(N):
            dp_i = min(h-A[i],H)
            dp[h] = min(dp[h],dp[dp_i]+B[i])
            if h >= H:
                minim = min(minim,dp[h])


    print(minim)
    # assert False


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
[H,N]=[int(i) for i in input().split()]
A=[0 for i in range(N)]
B=[0 for i in range(N)]
for n in range(N):
  [A[n],B[n]]=[int(i) for i in input().split()]
k=H+max(A)+1
DP=[100000000 for i in range(k)]
DP[0]=0
for n in range(N):
  for h in range(k):
    if h-A[n]>-1:
    	if DP[h-A[n]]+B[n]<DP[h]:DP[h]=DP[h-A[n]]+B[n]
print(min(DP[H:]))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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()))
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 = [0]*N, [0]*N
for i in range(N):
	A[i], B[i] = MAP()


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


for i in range(N):
	for j in range(H+1):
		if j < A[i]:
			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])

#for i in range(0, N+1):
#	print(dp[i])

print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

def main():
	H, N = MAP()
	A, B = [0]*N, [0]*N
	for i in range(N):
		A[i], B[i] = MAP()

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


	for i in range(N):
		for j in range(H+1):
			if j < A[i]:
				dp[i+1][j] = min(dp[i][j], B[i])
			if j>= A[i]:
				dp[i+1][j] = min(dp[i][j], dp[i][j-A[i]]+B[i], min([dp[i+1][j-A[i]*x] + B[i]*x for x in range(1, j//A[i] + 1)]))
			

	#for i in range(N+1):
	#	print(dp[i])

	print(dp[N][H])

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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()))
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 = [0]*N, [0]*N
for i in range(N):
	A[i], B[i] = MAP()

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


for i in range(N):
	for j in range(H+1):
		if j < A[i]:
			dp[i+1][j] = min(dp[i][j], B[i])
		if j>= A[i]:
			dp[i+1][j] = min(dp[i][j], dp[i][j-A[i]]+B[i], min([dp[i+1][j-A[i]*x] + B[i]*x for x in range(1, j//A[i] + 1)]))
			

#for i in range(N+1):
#	print(dp[i])

print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def dp(H, N, a, b):
  d = defaultdict(lambda: INF)
  d[0] = 0
  max_a = max(a)
  for h in range(1, H + max_a):
    d[h] = min([d[h - a[i]] + b[i] for i in range(N)])
  return min([d[H + h] for h in range(max_a)])

INF = 10 ** 10
H, N = map(int, input().split())
a = [0 for _ in range(N)]
b = [0 for _ in range(N)]
for i in range(N):
  ai, bi = map(int, input().split())
  a[i] = ai
  b[i] = bi
print(dp(H, N, a, b))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import deque
import math
import bisect
import sys
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


h,n=mp()
magic=[lmp() for i in range(n)]
dp=[float("inf")]*(h+1)
dp[0]=0
for i in range(h):
    for k in range(n):
        ni=min(i+magic[k][0],h)
        dp[ni]=min(dp[ni],dp[i]+magic[k][1])
print(dp[-1])

Submission status: Time Limit Exceeded

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


dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)
 
print(dp[-1])

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=[0]
AM=max(A)
BM=max(B)
for i in range(1,H+AM):
    dcand=dp[-1]+BM
    for j in range(N):
        dcand=min(dcand,B[j]+min(dp[i-A[j]:]))
    dp.append(dcand)

print(min(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=[0]
for i in range(1,H+max(A)):
    dcand=[]
    for j in range(N):
        dcand.append(B[j]+min(dp[i-A[j]:]))
    dp.append(min(dcand))

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
def main() -> None:
    H, N = rmi()
    AB = []
    for _ in range(N):
        AB.append(rmi())
    dp = [10 ** 9] * (H + 1)
    dp[0] = 0
    for damage, mp in AB:
        for i in range(len(dp)):
            prev = max(i - damage, 0)
            dp[i] = min(dp[i], dp[prev] + mp)
    w(dp[H])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main() -> None:
    H, N = rmi()
    AB = []
    for _ in range(N):
        AB.append(rmi())
    dp = [10 ** 9] * (H + 1)
    dp[0] = 0
    for damage, mp in AB:
        for i in range(len(dp)):
            prev = max(i - damage, 0)
            dp[i] = min(dp[i], dp[prev] + mp)
    w(dp[H])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 9)
    main()

Submission status: Time Limit Exceeded

Solution code:

h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, N = map(int, readline().split())
    Magic = list(list(map(int, readline().split())) for _ in range(N))

    dp = [INF]*(H+1)
    dp[0] = 0
    for h in range(H):
        for damage, cost in Magic:
            next_index = min(h + damage, H)
            dp[next_index] = min(dp[next_index],dp[h]+cost)
    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import maxsize

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

dp = [0] + [maxsize]*h
for a, b in m:
    for i in range(h+1):
        dp[min(i+a, h)] = min(dp[min(i+a, h)], dp[i]+b)
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
def abc153_e():
    H, N = map(int, input().split())
    M = [tuple(map(int, input().split())) for _ in range(N)]

    inf = 10**18
    cost = [inf] * (H+1)
    cost[0] = 0
    for a, b in M:
        for i in range(1, H+1):
            tmp = cost[i-a] + b if i-a > 0 else b
            cost[i] = min(cost[i], tmp)
    print(cost[H])

abc153_e()

Submission status: Time Limit Exceeded

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

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
h, n = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(n)]
h_max = 10 ** 4
inf = 10 ** 9
dp = [inf] * (h_max + 1)
dp[0] = 0
for h_target in range(1, h_max + 1):
    for attack, mp in AB:
        h_remain = max(0, h_target - attack)
        dp[h_target] = min(dp[h_target], dp[h_remain] + mp)
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
H, N = list(map(int, input().split()))
dp = [float('inf') for i in range(H + 1)]

dp[0] = 0 # 初期化
for i in range(N): #ナップザック問題の動的計画法
    A, B = list(map(int, input().split()))
    for j in range(1, H + 1):
        nj = max(j - A, 0) # 配列外参照防止
        dp[j] = min(dp[j], dp[nj] + B)
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
H, N = list(map(int, input().split()))
dp = [float('inf') for i in range(H + 1)]

dp[0] = 0 # 初期化
for i in range(N): #ナップザック問題の動的計画法
    A, B = list(map(int, input().split()))
    for j in range(H):
        nj = min(j + A, H) # 配列外参照防止
        dp[nj] = min(dp[nj], dp[j] + B)
print(dp[H])

Submission status: 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.append(a_)
    b.append(b_)
dp = [0] * (max(a) + h)
for i in range(1, max(a) + h):
    dp[i] = min(dp[i - a[j]] + b[j] for j in range(n))
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

INF = 10**10

h,n = nm()

dp = [INF] * (h+1)

dp[0] = 0

for i in range(n):
  a,b = nm()

  for j in range(h):
    nj = min(j+a,h) 
    dp[nj]=min(dp[nj],dp[j]+b) # ダメージがj+aの時のコスト

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(n)]
maxa=max([a for a,b in ab])
maxmp=pow(10,8)
dp=[maxmp]*(h+maxa) # dp[i]:ダメージをぴったりi与えるのに必要な最小魔力
dp[0]=0
for i in range(h+maxa):
  b=[dp[i-a]+b for a,b in ab if i-a>=0]
  dp[i]=min(dp[i],min(b)) if b else dp[i]
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))

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

for i in range(H):
    for a,b in magic:
        d=min(i+a,H)
        dp[d]=min(dp[d],dp[i]+b)
print(dp[H])

Submission status: Time Limit Exceeded

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

INF = 1e100

dp = [[INF] * (10 ** 4 + 1) for i in range(10 ** 3 + 1)]

dp[0][0] = 0

for i in range(n):
    a, b = map(int, input().split())
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j] , dp[i][j])
        dp[i+1][min(h, (j+a))] = min(dp[i+1][min(h, (j+a))], dp[i+1][j] + b)

print(dp[n][h])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
h,n,*ab = map(int,open(0).read().split())
ab = [(ab[i*2],ab[i*2+1]) for i in range(n)]
dp = [10**10 for _ in range(h)]
dp[0] = 0
ans = 10**10
for i in range(h):
  if dp[i] == 10**10:
    continue
  for j in range(n):
    nh = i+ab[j][0]
    nm = dp[i]+ab[j][1]
    if nh >= h:
      ans = min(ans,nm)
    else:
      dp[nh] = min(dp[nh],nm)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,n,*ab = map(int,open(0).read().split())
ab = [(ab[i*2],ab[i*2+1]) for i in range(n)]
dp = [10**10 for _ in range(h)]
dp[0] = 0
ans = 10**10
for i in range(h):
  for j in range(n):
    nh = i+ab[j][0]
    nm = dp[i]+ab[j][1]
    if nh >= h:
      ans = min(ans,nm)
    else:
      dp[nh] = min(dp[nh],nm)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,N=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxA=max(AB)[0]
#dp[i] ひとつ前までの呪文で体力iを削るために必要な最小魔法消費量
dp=[float("inf")]*(H+maxA)
ndp=[float("inf")]*(H+maxA)
dp[0]=0
for j in range(N):
    for i in range(H+1):
        ndp[i]=dp[i]
    cost=AB[j][1]
    fire=AB[j][0]
    for i in range(H+1):
        repeat=0
        while i+fire*repeat<H:
            repeat+=1
            ndp[i+fire*repeat]=min(dp[i]+cost*repeat,ndp[i+fire*repeat])
    dp=ndp[:]

ans=float("inf")
for i in range(H,H+maxA):
    ans=min(ans,dp[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,N=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxh=10**4
#dp[i] ひとつ前までの呪文で体力iを削るために必要な最小魔法消費量
dp=[float("inf")]*(2*maxh+1)
ndp=[float("inf")]*(2*maxh+1)
dp[0]=0
for j in range(N):
    for i in range(H+1):
        ndp[i]=dp[i]
    cost=AB[j][1]
    fire=AB[j][0]
    for i in range(H+1):
        repeat=0
        while i+fire*repeat<H:
            repeat+=1
            ndp[i+fire*repeat]=min(dp[i]+cost*repeat,ndp[i+fire*repeat])
    dp=ndp[:]

ans=float("inf")
for i in range(H,2*maxh+1):
    ans=min(ans,dp[i])
print(ans)

Submission status: Time Limit Exceeded

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

dp = [0]*(h+1)

for i in range(1,h+1):
    mn = 10**9
    for j in ab:
        hp = j[0]
        mp = j[1]  
        if i-hp<0:
            mn = min(mp,mn)
        else:
            mn = min(dp[i-hp]+mp, mn)
        dp[i] = mn

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
import sys

import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    h, n = ns()
    d = [na() for _ in range(n)]

    mat = [INF for _ in range(h + 1)]

    mat[0] = 0
    for i in range(h):
        if mat[i] == INF:
            continue
        for a, b in d:
            if i + a < h + 1:
                mat[i + a] = min(mat[i + a], mat[i] + b)
            else:
                mat[h] = min(mat[h], mat[i] + b)

    print(mat[h])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#初見じゃ無理だった。DPを使う
#標準入力
import math
import numpy as np
H, N = map(int, input().split())
AB = []
max_A = 0
for i in range(N):
    ab = list(map(int, input().split()))
    if max_A < ab[0] :
        max_A = ab[0]
    AB.append(ab)
AB = np.array(AB)

 #DP
DP = [0] * (H + max_A)
for i in range(1, H + max_A ): #DP[i] の最小値を求めていく
    tmp_mini = 10 ** 8
    for j in range(N):
        if i - AB[j][0] >= 0:
            tmp = DP[i - AB[j][0]] + AB[j][1]
            if tmp_mini > tmp:
                tmp_mini = tmp
    DP[i] = tmp_mini
print(min(DP[H: H + max_A]))

Submission status: Time Limit Exceeded

Solution code:
#初見じゃ無理だった。DPを使う
#標準入力
import math
H, N = map(int, input().split())
AB = []
max_A = 0
for i in range(N):
    ab = list(map(int, input().split()))
    if max_A < ab[0] :
        max_A = ab[0]
    AB.append(ab)

 #DP
DP = [0] * (H + max_A)
for i in range(1, H + max_A ): #DP[i] の最小値を求めていく
    tmp_mini = 10 ** 8
    for j in range(N):
        if i - AB[j][0] >= 0:
            tmp = DP[i - AB[j][0]] + AB[j][1]
            if tmp_mini > tmp:
                tmp_mini = tmp
    DP[i] = tmp_mini
print(min(DP[H: H + max_A]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
h , n = map(int,input().split())
maho = []
for i in range(n):
    a,b = map(int,input().split())
    maho.append((a,b))
dp = [10**9 for i in range(h+1)]
for i in range(1,h+1):
    for a,b in maho:
        if i <= a:
            dp[i] = min(dp[i],b)
        elif i > a:
            dp[i] = min(dp[i],dp[i-a]+b)

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
HN = list(map(int, input().split()))
H = HN[0]; N = HN[1]
AB = [list(map(int, input().split())) for _ in range(N)]
 
DP = [[0]*H for i in range(N)]
 
for i in range(H):
    DP[0][i] = int((1+i//AB[0][0])*AB[0][1])
 
for i in range(1,N):
    for j in range(H):
        if j<AB[i][0]:
            DP[i][j] = int(min([DP[i-1][j], AB[i][1]]))
        else:
            DP[i][j] = min([DP[i-1][j], DP[i][j-AB[i][0]] + AB[i][1]])
 
print(int(DP[N-1][H-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
HN = list(map(int, input().split()))
H = HN[0]; N = HN[1]
AB = [list(map(int, input().split())) for _ in range(N)]
 
DP = np.zeros((N,H))
 
for i in range(H):
    DP[0][i] = int((1+i//AB[0][0])*AB[0][1])
 
for i in range(1,N):
    for j in range(H):
        if j<AB[i][0]:
            DP[i][j] = int(min([DP[i-1][j], AB[i][1]]))
        else:
            DP[i][j] = min([DP[i-1][j], DP[i][j-AB[i][0]] + AB[i][1]])
 
print(int(DP[N-1][H-1]))

Submission status: Time Limit Exceeded

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

ab=[]
dp=[0]*(10**5)

for _ in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
    dp[b]=a

#dp[b]は、自分がダメージをｂ受けた時の、相手に与えたダメージ
i=1
while 1:

    dp[i]=max(dp[i],dp[i-1])
    for k in range((i-1)//2+2):
        dp[i]=max(dp[i],dp[k]+dp[i-k])
    
    #print(dp)
    if dp[i]>=h:
        print(i)
        exit()
    i+=1

Submission status: Time Limit Exceeded

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


main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(200000)

H,N = map(int, input().split()) #H<=10**4,N<=10**3

AB_dict = dict() #A:Atack power, B:Consumption MP

for i in range(N): #N<=10**3
    A,B = map(int, input().split())
    if A not in AB_dict:
        AB_dict[A] = B
    else:
        if B < AB_dict[A]: #同じ攻撃力なら消費MPが少ない方を優先する
            AB_dict[A] = B

@lru_cache(maxsize=None)
def get_consumption_MP(HP): #HPを削るのに必要なMPを求める関数
    ans = 10**9 + 7
    
    for AB in AB_dict.items():
        A = AB[0]
        B = AB[1]
        
        if A >= HP:
            if B < ans:
                ans = B
        else:
            if B + get_consumption_MP(HP-A) < ans:
                ans = B + get_consumption_MP(HP-A)
                
    return ans
        
print(get_consumption_MP(H))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,n=map(int,input().split())
    lis=[]
    for i in range(n):
        lis.append(tuple(map(int,input().split())))
    dp=[10**10]*(h+1)
    dp[0]=0
    for l in lis:
        a,b=l[0],l[1]
        for i in range(1,h+1):
            dp[i]=min(dp[i],min(dp[max(i-a,0):i])+b)
    print(dp[h])



if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from operator import itemgetter
def main():
    h,n=map(int,input().split())
    lis=[]
    for i in range(n):
        lis.append(tuple(map(int,input().split())))
    lis.sort(key=itemgetter(1))
    dp=[10**10]*(h+1)
    dp[0]=0
    for l in lis:
        a,b=l[0],l[1]
        for i in range(1,h+1):
            dp[i]=min(dp[i],min(dp[max(i-a,0):i])+b)
    print(dp[h])



if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
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())
min_hp = h
max_hp = h + max(A)

dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0

for i in range(1, max_hp + 1):
    dp[i] = min(dp[i - A[j]] + B[j] for j in range(n))
print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

H,N = inputIL()
M = inputILL(N)


cospa = max(a/b for a,b in M)
MAXJ = math.floor(10000/cospa + 1)

dp = [[0 for j in range(MAXJ)] for i in range(N)]
a0, b0 = M[0]
dp[0] = [(j//b0)*a0 for j in range(MAXJ)]

for i in range(1,N):
  a,b = M[i]
  for j in range(MAXJ):
    if j < b:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j] , dp[i-1][j-b]+a, dp[i][j-b]+a)

import bisect
print(bisect.bisect_left(dp[-1],H))

Submission status: Time Limit Exceeded

Solution code:
import sys
h, n = map(int, input().split())
# A = [0] * n
# B = [0] * n
AB = [list(map(int, input().split())) for _ in range(n)]
# for i in range(n):
#     A[i], B[i] = map(int, input().split())
min_hp = h

dp = [sys.maxsize] * (min_hp + 1)
dp[0] = 0

for i in range(0, min_hp + 1):
    for ab in AB: # type of spell
        next_index = min(i + ab[0], min_hp)
        dp[next_index] = min(dp[next_index], dp[i] + ab[1])

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:

H, N = map(int, input().split())
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]

# dp[damage] := モンスターに damage を与えるために必要な最小コスト
dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
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())
min_hp = h

dp = [sys.maxsize] * (min_hp + 1)
dp[0] = 0

for i in range(0, min_hp + 1):
    for j in range(n): # type of spell
        next_index = min(i + A[j], min_hp)
        dp[next_index] = min(dp[next_index], dp[i] + B[j])

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
import sys
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())
min_hp = h
max_hp = h + max(A)

dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0

for i in range(0, min_hp + 1):
    for j in range(n): # type of spell
        next_index = min(i + A[j], min_hp)
        dp[next_index] = min(dp[next_index], dp[i] + B[j])

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
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())
min_hp = h
max_hp = h + max(A)

dp = [sys.maxsize] * (max_hp + 2)
dp[0] = 0

for i in range(0, min_hp + 1):
    for j in range(n): # type of spell
        dp[i + A[j]] = min(dp[i + A[j]], dp[i] + B[j])

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

ab = []
max_a = 0
min_a = 10001
for i in range(N):
    a, b = map(int, input().split())
    if a > max_a:
        max_a = a
    if a < min_a:
        min_a = a
    ab.append([a, b])

# print(max_a, min_a)
inf = float('inf')
dp = [inf for _ in range(H + max_a)]

for a, b in ab:
    for i in range(1, len(dp)):
        # 魔法aだけで体力iを減らすために魔法を使う回数
        times = i // a + (0 if i % a == 0 else 1)
        # 使う魔力
        power = b * times
        if i - a > 0:
            power = min(power, dp[i - a] + b)
        dp[i] = min(dp[i], power)

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, N = map(int, input().split())

dp = [float('inf')]*(H+1)
dp[0] = 0
for i in range(N):
    a, b = map(int, input().split())
    dp[1:a+1] = np.minimum(dp[1:a+1], b)
    for j in range(a+1, H+1):
        dp[j] = min(dp[j], dp[j-a]+b)
print(int(dp[-1]))