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:
from sys import stdin
from sys import  setrecursionlimit
setrecursionlimit(300000)

[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)]*(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: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
ATK, MP = zip(*(tuple(map(int, input().split())) for _ in range(N)))
MAX_ATK = max(ATK)
table = [0] * (H + MAX_ATK)
for damage in range(1, H + 1):
    table[damage] = min(table[damage - ATK[magic]] + MP[magic] for magic in range(N))
print(table[H])

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
ATK, MP = zip(*(tuple(map(int, input().split())) for _ in range(N)))
table = [[float("inf")] * (H + 1) for _ in range(N + 1)]
table[0][0] = 0
for magic in range(N):
    for damage in range(H + 1):
        now = table[magic][damage]
        table[magic + 1][damage] = min(now, table[magic + 1][damage])
        table[magic][min(H, damage + ATK[magic])] = min(now + MP[magic], table[magic][min(H, damage + ATK[magic])])

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

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
hpdown = list()
mpdown = list()
for i in range(N):
  a, b = map(int, input().split())
  hpdown.append(a)
  mpdown.append(b)
  
hmax = max(max(mpdown)*2+1, H+max(mpdown)+1)
dp = [10 ** 9] * (hmax)
dp[0] = 0
for h in range(1, hmax):
  for n in range(N):
    if(h-hpdown[n]>=0):
      dp[h] = min(dp[h], dp[h-hpdown[n]] + mpdown[n])
      
ans = 10 ** 9
for i in range(H, hmax):
  if(dp[i] < ans):
    ans = dp[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


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)

    INF = 1000000005
    dp = [INF for _ in range(H + 1)]
    dp[0] = 0
    for i in range(0, H + 1):
        for j in range(N):
            k = 0
            while i + k * A[j] < H:
                dp[i + k * A[j]] = min(dp[i + k * A[j]], dp[i] + k * B[j])
                k += 1
            dp[H] = min(dp[H], dp[i] + k * B[j])

    print(dp[H])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

attack_list = []
mp_list = []
for i in range(N):
    a, m = map(int, input().split())
    attack_list.append(a)
    mp_list.append(m)

inf = float('inf')
max_hp = H+max(attack_list)
dp = [inf for i in range(max_hp)]
dp[0] = 0

for i in range(H):
    for j in range(N):
        next_i = i + attack_list[j]
        dp[next_i] = min(dp[next_i], dp[i] + mp_list[j])

print(min(dp[H:max_hp+1]))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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)

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

    for h in range(0, H):
        for a, b in zip(A, B):
            tmp = dp[h] + b
            if h + a >= H and tmp < dp[H]:
                dp[H] = tmp
            elif h + a < H and tmp < dp[h + a]:
                dp[h + a] = tmp

    print(dp[-1])


if __name__ == "__main__":
    main()

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 = [float("inf")] * (H + 1)
dp[0] = 0

for h in range(0, H):
    for a, b in zip(A, B):
        tmp = dp[h] + b
        if h + a >= H and tmp < dp[H]:
            dp[H] = tmp
        elif h + a < H and tmp < dp[h + a]:
            dp[h + a] = tmp

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
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 rem <= 0:
        return 0
    elif mem[rem-1]:
        return mem[rem-1]
    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: Time Limit Exceeded

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

dp = [float("inf") for _ in range(H+1)]

dp[H] = 0

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = [-1]*(H + 1)
    dp[0] = 0
    for i in range(N):
        a = AB[2 * i + 0]
        b = AB[2 * i + 1]
        for i in range(H + 1):
            d = dp[i] + b
            if dp[i] != -1:
                j = i + a
                if j > H:
                  j = H
                if dp[j] == -1 or d < dp[j]:
                    dp[j] = d
    print(dp[H])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
###### Importing Libraries ######
import math
import operator as op
from functools import reduce
from fractions import Fraction as frac
#################################
##### User defined function #####

############ NCR ###############
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
    
############ READ ###############
def rd(p):
    if(p==0):
        return input()
    if(p==1):
        return int(input())
    if(p==2):
        return map(int,input().split())
    if(p==3):
        return list(map(int,input().split()))


############ DSU ###############
global par
# par=[-1 for i in range(100001)]
# t=rd(1)
def find(u):
    if(par[u]<0):
        return u
    else:
        return find(par[u])
def uni(x,y):
    u=find(x)
    v=find(y)
    if u==v:
        return
    if(par[u]<par[v]):
        par[u]+=par[v]
        par[v]=u
    else:    
        par[v]+=par[u]
        par[u]=v
################################        
        

t=1
for term in range(1,t+1):
    h,n=rd(2)
    P=[rd(3) for i in range(n)]
    x=max(a for a,b in P)
    DP=[0 for i in range(h+x)]
    for i in range(1,h+x):
        DP[i]=min(DP[max(i-a,0)]+b for a,b in P)
    print(DP[h])

Submission status: Time Limit Exceeded

Solution code:
###### Importing Libraries ######
import math
import operator as op
from functools import reduce
from fractions import Fraction as frac
#################################
##### User defined function #####

############ NCR ###############
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
    
############ READ ###############
def rd(p):
    if(p==0):
        return input()
    if(p==1):
        return int(input())
    if(p==2):
        return map(int,input().split())
    if(p==3):
        return list(map(int,input().split()))


############ DSU ###############
global par
par=[-1 for i in range(100001)]
# t=rd(1)
def find(u):
    if(par[u]<0):
        return u
    else:
        return find(par[u])
def uni(x,y):
    u=find(x)
    v=find(y)
    if u==v:
        return
    if(par[u]<par[v]):
        par[u]+=par[v]
        par[v]=u
    else:    
        par[v]+=par[u]
        par[u]=v
################################        
        

t=1
for term in range(1,t+1):
    h,n=rd(2)
    P=[rd(3) for i in range(n)]
    x=max(a for a,b in P)
    DP=[0 for i in range(h+x)]
    for i in range(1,h+x):
        DP[i]=min(DP[max(i-a,0)]+b for a,b in P)
    print(DP[h])

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = [-1]*(H + 1)
    dp[0] = 0
    for i in range(N):
        a = AB[2 * i + 0]
        b = AB[2 * i + 1]
        for i in range(H + 1):
            d = dp[i] + b
            if dp[i] != -1:
                j = i + a
                j = min(j, H)
                if dp[j] == -1 or d < dp[j]:
                    dp[j] = d
    print(dp[H])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    h, n = input_to_int_map()
    ab = [input_to_int_tuple() for i in range(n)]

    x = max(a for a, b in ab)

    dp = [0] * (h + x)
    for i in range(1, h + 1):

        min_val = 9999999999
        for a, b in ab:
                min_val = min(min_val, dp[i - a] + b)

        dp[i] = min_val

    return dp[h]


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

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+1)
for i in range (1,H+1):
    dp[i]=min(dp[max(i-a,0)]+b for a,b in ab)
print(dp[H])

Submission status: Time Limit Exceeded

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

# dp[i]: 体力iにするための最小魔力
dp = [float("inf")] * (H + 1)

# 初期条件
dp[H] = 0

for i in range(H, -1, -1):
    for a, b in AB:
        HP = max(0, i - a)
        dp[HP] = min(dp[HP], dp[i] + b)

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(n)]
A = [a for a, b in AB]
B = [b for a, b in AB]
inf = 10**10
# DP[i][j]=i個以内で体力j以上削るための消費魔力の最小値
DP = [[inf for j in range(h+1)] for i in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    for j in range(h+1):
        DP[i][j] = min(DP[i-1][j], DP[i][max(0, j-A[i-1])]+B[i-1])
print(DP[n][h])

Submission status: Time Limit Exceeded

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)
amax, _ = magic[0]

INF = 1<<60

def solve():
    btab = [INF] * (H+1)
    btab[0] = 0
    for h in range(1, min(amax, H)+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: Time Limit Exceeded

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

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

Solution code:
INF = 10 ** 9

def main():
    H, N = map(int, input().split())
    dp = [INF] * (H+1)
    dp[0] = 0
    for _ 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])

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

A = []
B = []
for i in range(N):
    A.append(C[i][0])
    B.append(C[i][1])

M = max(A)
m = min(A)

dp = {} #dp[h]は体力をh減らすのに必要な魔力の最小値

for i in range(-M+1,1):
    dp[i] = 0

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

print(min(dp[i] for i in range(H,H+m)))

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
dp = [10 ** 100] * H
for _ in range(N):
    A, B = map(int, input().split())
    for i in range(H - 1, -1, -1):
        if A + i >= H:
            dp[i] = min(dp[i], B)
        else:
            dp[i] = min(dp[i], dp[A + i] + B)
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
H,N = map(int,input().split())
dp = [float('INF')]*(H+1)
dp[0]=0
for _ in range(N):
    a,b = map(int,input().split())
    for i in range(1,H+1):
        dp[i]=min(dp[max(i-a,0)]+b,dp[i])

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, n = map(int, readline().split())
ab = [list(map(int, readline().split())) for i in range(n)]
inf = float('inf')
dp = [inf] * (2 * 10 ** 4)
dp[0] = 0
for a, b in ab:
    for n in range(h):
        if dp[n + a] > dp[n] + b:
            dp[n + a] = dp[n] + b

ans = min(dp[h:])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, n = map(int, readline().split())
ab = [list(map(int, readline().split())) for i in range(n)]
inf = float('inf')
dp = [inf] * (h + 1)
dp[0] = 0
for i in range(n):
    for k in range(h):
        if dp[k] != inf:
            for j in range(1, h + 1):
                if ab[i][0] * j + k < h:
                    dp[j * ab[i][0] + k] = min(dp[k] + ab[i][1] * j, dp[j * ab[i][0] + k])
                else:
                    dp[-1] = min(dp[k] + ab[i][1] * j, dp[-1])
                    break
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
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())
    for j in range(1,H+1):
        dp[j] = min(dp[j],dp[max(j-a,0)]+b)

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
H,N=map(int,input().split(' '))
Magics = [list(map(int,input().split(' '))) for i in range(N)]
dp=[float('inf')]*(H+1)
dp[0]=0
for i in range(H+1):
    for a,b in Magics:
        if i+a<=H:
            dp[i+a]=min(dp[i+a],dp[i]+b)
        else:
            dp[H]=min(dp[H],dp[i]+b)
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
H,N=map(int,input().split(' '))
Magics = [list(map(int,input().split(' '))) for i in range(N)]
dp=[float('inf')]*(H+1)
dp[H]=0
for i in range(H,-1,-1):
    for a,b in Magics:
        if 0<=i-a<=H:
            dp[i-a]=min(dp[i-a],dp[i]+b)
        else:
            dp[0]=min(dp[0],dp[i]+b)
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import copy

H,N=map(int,input().split())
A=[]
B=[]
for _ in range(N):
    a,b=map(int,input().split())
    A.append(copy.copy(a))
    B.append(copy.copy(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: Time Limit Exceeded

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

dp = [float('inf')]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp_val = dp[i]
    for a, m in am:
        if a >= i:#overkill
            dp_val = min(dp_val, m)
        else:
            dp_val = min(dp_val, dp[i-a]+m)
    dp[i] = dp_val
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
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())
    for j in range(1,H+1):
        dp[j] = min(dp[j],dp[max((j-a),0)]+b)

print(dp[-1])

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)
F = [0]
for i in range(1, h+1):
    f = 1 << 30
    for a, b in zip(A, B):
        if i < a:
            f = min(f, b)
        else:
            f = min(f, F[i-a]+b)
    F.append(f)
print(f)

Submission status: Time Limit Exceeded

Solution code:
H,N = map(int,input().split())
dp = [[[0,float('INF')]for i in range(H+1)] for _ in range(N+1)]
#↑[ダメージ、MP]

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

# dp[i][j] -> iまでの魔法が使えるとき、j以上のダメージを与えるための最小限のMP
for i in range(1,N+1):
    a,b = map(int,input().split())
    for j in range(1,H+1):
        """
        その魔法を使わない場合のdp[i][j]
        dp[i-1][j]とdp[i][j-1]のうち、MPが若いものを使う。
        ただし、dp[i][j-1]に関しては、ダメージ(dp[i][j-1][0])がj未満の場合、使わない
        """
        dp[i][j] = dp[i-1][j][:]
        if dp[i][j-1][0] >= j and dp[i][j-1][1] < dp[i][j][1]:
            dp[i][j] = dp[i][j-1][:]
        
        """
        その魔法を使う場合のdp[i][j]
        j-a<=0の場合、dp[i][j]は
        dp[i][j]と[a,b]のうち、MPが若いものを使う。
        j-a>0の場合は、
        dp[i][j]とdp[i][j-a][1]+b,dp[i-1][j-a][1]+bのうち、MPが若いものを使う。
        """
        if j-a<=0:
            if b < dp[i][j][1]:
                dp[i][j]=[a,b]

        else:
            if dp[i][j-a][1]+b <= dp[i][j][1] and dp[i][j-a][1]+b <= dp[i-1][j-a][1]+b:
                dp[i][j]=[dp[i][j-a][0]+a,dp[i][j-a][1]+b]
            elif dp[i-1][j-a][1]+b <= dp[i][j][1] and dp[i-1][j-a][1]+b <= dp[i][j-a][1]+b:
                dp[i][j]=[dp[i-1][j-a][0]+a,dp[i-1][j-a][1]+b]


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

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
    a_sub,b_sub=map(int,input().split())
    a.append(a_sub)
    b.append(b_sub)
inf=10000000000000
ma=max(a)
dp=[inf]*(h+1+ma)
dp[0]=0
for i in range(n):
    x=[a[i],b[i]]
    for j in range(h+1+ma):
        if dp[j]!=inf:
            if j+x[0]<=h+ma:
                dp[j+x[0]]=min(dp[j+x[0]],dp[j]+x[1])
            else:
                break
print(min(dp[h:]))

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

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

dp[0] = 0

for a,b in AB:
    for i in range(H):
        ni = min(i+a,H)
        dp[ni] = min(dp[ni], dp[i]+b)

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
[H,N] = [int(s) for s in input().rstrip().split(' ')] #HもんすたーのHP,N魔法の種類
L_1 = []
L_2 = []
for i in range(N):
    A_i = [int(s) for s in input().rstrip().split(' ')] #[攻撃力,消費魔力]
    L_1.append(A_i[0])
    L_2.append(A_i[1])
M = [10**8 for x in range(H+max(L_1))] #最小消費魔力
M[0] = 0
for k in range(1,H+max(L_1)):
  for n in range(N):
     M[k] = min(M[k],L_2[n]+M[max(k-L_1[n],0)])
print(min(M[H:]))

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
m=[list(map(int,input().split())) for i in range(n)]
dp=[10**8]*(h+1) #min MP for i damage
dp[0]=0
for i in range(n):
  for j in range(h):
    ctr=0
    while j-ctr*m[i][0]>=m[i][0]:
      ctr+=1
      dp[j]=min(dp[j],dp[j-ctr*m[i][0]]+m[i][1]*ctr)
  ctr=0
  while h>ctr*m[i][0]:
    ctr+=1
    for j in range(h,h+ctr*m[i][0]):
      dp[h]=min(dp[h],dp[max(0,j-ctr*m[i][0])]+m[i][1]*ctr)
print(dp[h])

Submission status: Time Limit Exceeded

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):
      if j>=a*k:
        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]
      else:
        mana = b*k
        damage = a*k
        if dp[i][j][0] > mana:
          dp[i][j]=[mana,damage]

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

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[j] != 1e10:
            dp[min(j + A, H)] = min(dp[min(j + A, H)], dp[j] + B)
print(dp[H])

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[j] != float('inf'):
            dp[min(j + A, H)] = min(dp[min(j + A, H)], 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 = [10**9] * (h+1)
dp[0] = 0
 
for i in range(1, h+1):
    for j in range(n):
        dp[i] = min(dp[i], dp[max(i-a[j], 0)] + b[j])
 
print(dp[-1])

Submission status: Time Limit Exceeded

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

H, N = map(int, input().split(" "))
dp = [[float('inf') for i in range(H + 1)] for j in range(N + 1)]
for i in range(N + 1):
    dp[i][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][min(j + A, H)] = min(dp[i][min(j + A, H)], dp[i][j] + B)
print(dp[N][H])

Submission status: Time Limit Exceeded

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

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[i][j] != float('inf'):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            dp[i][min(j + A, H)] = min(dp[i][min(j + A, H)], dp[i][j] + B)
print(dp[N][H])

Submission status: Time Limit Exceeded

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

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[i][j] != float('inf'):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            dp[i][min(j + A, H)] = min(dp[i][min(j + A, H)], dp[i][j] + B)
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_, b_ = map(int, input().split())
    a.append(a_)
    b.append(b_)

dp = [10**9] * (h+1)
dp[0] = 0

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
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)

dp = [[float('inf') for i in range(H+max(A))] for j in range(N+1)]
dp[0][0] = 0

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


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

Submission status: Time Limit Exceeded

Solution code:
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)

dp = [float('inf') for i in range(H+max(A))]
dp[0] = 0

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

print(min(dp[H:]))

Submission status: Time Limit Exceeded

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

import sys
from functools import lru_cache

@lru_cache(maxsize=20000)
def minimum_mp_used_for_damage(d):
    if d <= 0:
        return 0
    res = 10 ** 9
    for i in range(n):
        res = min(res, b[i] + minimum_mp_used_for_damage(d - a[i]))
    return res

sys.setrecursionlimit(10 ** 6)
h, n = map(int, input().split())
a = []
b = []
for i in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)
print(minimum_mp_used_for_damage(h))

Submission status: Time Limit Exceeded

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

dp = [float('inf')] * (h + a_max)
dp[0] = 0
for i in range(h):
    for a, b in magic:
        if i + a > h + a_max:
            continue
        dp[i + a] = min(dp[i] + b, dp[i + a])

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
import sys

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)

sys.setrecursionlimit(10 ** 7)
# 入力: 体力, 出力: 魔力の最小値
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: Time Limit Exceeded

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(10001)]
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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

inf = float('INF')
dp = [inf for i in range(h+1)]
dp[0] = 0
for i in range(n):
    a,b = map(int, input().split())
    for j in range(h+1):
        # print(j+a)
        if j + a <= h and dp[j+a] > dp[j] + b:
            dp[j+a] = dp[j] + b
        elif j + a > h and dp[h] > dp[j] + b:
            dp[h] = dp[j] + b

print(dp[h])
# print(dp)

Submission status: Time Limit Exceeded

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

magic_min = [0 for _ in range(H+1)]
for i in range(H+1):
    if i != 0 and magic_min[i] == 0:
        continue
    for A, B in magic:
        Index = i + A
        value = magic_min[i] + B
        try:
            if magic_min[Index] == 0:
                magic_min[Index] = value
            elif value < magic_min[Index]:
                magic_min[Index] = value
        
        except:
            if magic_min[-1] == 0:
                magic_min[-1] = value
            elif value < magic_min[-1]:
                magic_min[-1] = value
                
print(magic_min[-1])

Submission status: Time Limit Exceeded

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

max_a = max(a)[0]

dp = [float('inf') for i in range(h + max_a + 1)]
dp[0] = 0
for i in range(1, h+max_a + 1):
    dp_ = dp[i]
    for damage in a:
        if i < damage[0]:
            dp_ = min(dp_, damage[1])
        else:
            dp_ = min(dp_, dp[i-damage[0]] + damage[1])
    dp[i] = dp_

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
H,N=map(int,input().split())
dp=[10**12 for _ in range(H+1)]
dp[0]=0
for i in range(N):
  h,n=map(int,input().split())
  for j in range(H+1):
    dp[j]=min(dp[j],dp[max(0,j-h)]+n)
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
H,N=map(int,input().split())
hn=[]
for i in range(N):
  hn.append(list(map(int,input().split())))
dp=[[10**17]*(H+1) for _ in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
  for j in range(H+1):
    h,n=hn[i-1][0],hn[i-1][1]
    dp[i][j]=min(dp[i-1][j],dp[i][max(0,j-h)]+n)
print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
MAX_LIMIT = 1e30
H, N = list(map(int, input().split()))
A, B = [], []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)  # HP
    B.append(b)  # power

# dp[i] means minimum power used to reduce HP i
dp = [MAX_LIMIT] * (H + max(A))
dp[0] = 0

for i in range(1, H + max(A)):
    cands = []
    for a, b in zip(A, B):
        if i - a >= 0:
            cands.append(b + dp[i - a])
    if len(cands) == 0:
        dp[i] = MAX_LIMIT  # we cannot directly reach this point
    else:
        dp[i] = min(cands)

# print(dp)
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())

a_max = max(a)
# dp[i] : モンスターのHPをi減らすのに必要な魔力の最小値
dp = [0] * (h + a_max + 1)
dp[0] = 0

for i in range(1, h + a_max + 1):
    m = 10 ** 9
    for j in range(n):
        tmp = dp[i - a[j]] + b[j]
        if (m > tmp):
            m = tmp

    dp[i] = m

print(min(dp[h:]))