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:
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

dp = [10**9 for _ in range(H+10**4+1)]
dp[0] = 0

for a, b in magic:
    for j in range(H+1):
        if dp[j+a] > dp[j] + b:
            dp[j+a] = dp[j] + b

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
# AtCoder Beginner Contest 153
# E - Crested Ibis vs Monster
# https://atcoder.jp/contests/abc153/tasks/abc153_e
H, N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*2)

INF = 1 << 30
dp = [INF]*(H+1)
dp[0] = 0
for i, (a, b) in enumerate(A):
    for h in range(H+1):
        mh = min(H, h+a)
        dp[mh] = min(dp[mh], dp[h] + b)
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
ab=[[] for i in range(n)]
for i in range(n):
  ab[i]=list(map(int,input().split()))
  
dp=[100000000 for i in range(h+1)]
dp[0]=0
for hi in range(h):
  for i in range(n):
    damage=min(h,hi+ab[i][0])
    dp[damage] = min(dp[damage],dp[hi]+ab[i][1])
    #print(damage,dp[damage],dp[hi]+ab[i][1])
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
# Problem E - Crested Ibis vs Monster

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

# initialization
mp_list = [float('INF')] * (H+1)
mp_list[0] = 0

# dp
for i in range(1, H+1):
    for ab in ab_pattern:
        a = ab[0]
        b = ab[1]
        if i-a>=0:
            mp_list[i] = min(mp_list[i], mp_list[i-a] + b)
        else:
            mp_list[i] = min(mp_list[i], mp_list[0] + b)

# output
print(mp_list[H])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

for _ in range(n):
  a, b = map(int, input().split())
  for i in range(a, len(dp)):
    dp[i] = min(dp[i-a]+b, dp[i])

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
from copy import deepcopy
from collections import deque
def main():
    h, n = map(int, input().split())
    a = deque()
    b = deque()
    aa = a.append
    ba = b.append
    for _ in range(n):
        numa, numb = map(int, input().split())
        aa(numa)
        ba(numb)
    dp = [10**9] * (h + 1)
    dp[0] = 0
    while a:
        dp_c = deepcopy(dp)
        at = a.popleft()
        bt = b.popleft()
        for i1 in range(h + 1):
            if i1 <= at:
                dp[i1] = min(bt, dp_c[i1])
            else:
                dp[i1] = min(dp[i1], dp[i1 - at] + bt)
    print(dp[h])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
readline= sys.stdin.readline
h,n=map(int,input().split())
li=[]
for i in range(n):
    li.append(list(map(int,readline().split())))
dp=np.zeros((n,h+1),dtype=int)
for i in range(h+1):
    if i%li[0][0]==0:
        dp[0][i]=(i//li[0][0])*li[0][1]
    else:
        dp[0][i]=(i//li[0][0]+1)*li[0][1]
for i in range(1,n):
    for j in range(h+1):
        if j==0:
            dp[i][j]=0
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-li[i][0],0)]+li[i][1])
print(dp[n-1][h])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,n=map(int,input().split())
li=[]
for i in range(n):
    li.append(list(map(int,input().split())))
dp=np.zeros((n,h+1),dtype=int)
for i in range(h+1):
    if i%li[0][0]==0:
        dp[0][i]=(i//li[0][0])*li[0][1]
    else:
        dp[0][i]=(i//li[0][0]+1)*li[0][1]
for i in range(1,n):
    for j in range(h+1):
        if j==0:
            dp[i][j]=0
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-li[i][0],0)]+li[i][1])
print(dp[n-1][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())

dp = [[1e18] * (h + 1) for _ in range(n + 1)]
dp[0][0] = 0

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

print(dp[n][h])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from copy import deepcopy
from collections import deque
def main():
    h, n = map(int, input().split())
    a = deque()
    b = deque()
    aa = a.append
    ba = b.append
    for _ in range(n):
        numa, numb = map(int, input().split())
        aa(numa)
        ba(numb)
    dp = [10**9] * (h + 1)
    dp[0] = 0
    while a:
        dp_c = deepcopy(dp)
        at = a.popleft()
        bt = b.popleft()
        for i1 in range(h + 1):
            if i1 <= at:
                dp[i1] = min(bt, dp_c[i1])
            else:
                dp[i1] = min(dp_c[i1], dp[i1 - at] + bt)
    print(dp[h])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
limit = H + max(A[i][0] for i in range(N))
dp = [int(1e18) for _ in range(limit+1)]
dp[0] = 0
for i in range(1, limit+1):
  for j in range(N):
    if A[j][0] > i:
      dp[i] = min(dp[i], A[j][1])
    else:
      dp[i] = min(dp[i], dp[i-A[j][0]]+A[j][1])
M = min(dp[i] for i in range(H, limit+1))
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:

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

max_a = max(a for a,b in ab_list)
W = H + 1 + max_a
dp = [0] * W

for i in range(W):
    dp[i] = 10**9
    for a,b in ab_list:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H-1:]))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
def main():
    h, n = map(int, input().split())
    
    inf = float('inf')
    dp = [inf] * (h + 1)
    dp[0] = 0
    for _ in range(n):
        a, b = map(int, input().split())
        dp_c = deepcopy(dp)
        for i1 in range(h + 1):
            if i1 <= a:
                dp[i1] = min(b, dp_c[i1])
            else:
                dp[i1] = min(dp_c[i1], dp[i1 - a] + b)
    print(dp[h])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
def main():
    h, n = map(int, input().split())
    magics = [tuple(map(int, input().split())) for _ in range(n)]

    inf = float('inf')
    dp = [inf] * (h + 1)
    dp[0] = 0
    for magic in magics:
        dp_c = deepcopy(dp)
        for i1 in range(h + 1):
            if i1 <= magic[0]:
                dp[i1] = min(magic[1], dp_c[i1])
            else:
                dp[i1] = min(dp_c[i1], dp[i1 - magic[0]] + magic[1])
    print(dp[h])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int,input().split())
data = []
ans = 0
M = -1
for _ in range(n):
    a,b = map(int,input().split())
    data.append((a,b))
    M = max(a,M)
dp = [float("inf") for _ in range(h+M)]
dp[0] = 0
for i,j in data:
    for k in range(h+M-1):
        if k+i <= h+M-1:
            dp[k+i] = min(dp[k]+j,dp[k+i])
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()
INF = 10 ** 9 + 7

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


def solve():

    dp = [INF] * (H + 1)
    dp[H] = 0

    for h in range(H, 0, -1):

        if dp[h] == INF:
            continue
        next_dp = dp

        for i in range(N):
            a, b = AB[i]
            hh = max(0, h - a)
            next_dp[hh] = min(dp[hh], dp[h] + b)

        dp = next_dp

    print(dp[0])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int, input().split()))
HP = a[0]

x = []
for i in range(a[1]):
    x1, y1 = [int(i) for i in input().split()]
    x.append((x1, y1))

max_tup = max(x, key=lambda x: x[0]) #最高攻撃力の呪文を記憶
max_a = max_tup[0] #その攻撃力を記録
#1次元　横：与えるダメージ　中身：最小魔力
dp = [10**10] * (HP + max_a)  #DP表はHP+最高攻撃力
dp[0] = 0

for i in range(1, len(dp)):
    for a, b in x:
        if i >= a:
            dp[i] = min(dp[i],dp[i - a] + b )

print(min(dp[HP:]))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.read

def main(H, N, tmp):
    damage = tmp[::2]
    magic = tmp[1::2]
    DP = [float('inf')] * 20001
    DP[0] = 0
    for i in range(20001):
        for j in range(N):
            s = i - damage[j]
            if s >= 0:
                DP[i] = min(DP[i], DP[s] + magic[j])
    return min(DP[H:])


if __name__ == "__main__":
    H, N, *tmp = map(int, input().split())
    ans = main(H, N, tmp)
    print(ans)

Submission status: Time Limit Exceeded

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

#dp　横を合計攻撃力　中身を最小魔力とする
dp = [100000000] * (h + 10 ** 4 + 1)
#hpを0減らすのに必要な魔力は0
dp[0] = 0

for i in range(h):
    if dp[i] == 100000000:#初期値の場合は更新しない
        continue

    for a, b in ab:#aがアタック bが使用魔力
        t = dp[i] + b #n番目の呪文を使った時、合計の魔力はtとなる
        if t < dp[i + a]: #今入っている魔力が新しい魔力よりも高いとき更新
            dp[i + a] = t
#print(dp)
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int,input().split())
li2=[input() for i in range(n)]
ab = []
w = 10 ** 10
for i in range(n):
    ab.append( [int(x.strip()) for x in li2[i].split()])
    w_sub = (int(h / ab[i][0]) + 1) * ab[i][1]
    if w_sub < w:
        w = w_sub

dp = [[0] * (w+1) for i in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j < ab[i][1]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i+1][j-ab[i][1]]+ab[i][0])

ans = 0
for i in range(w+1):
    if dp[n][i] >= h:
        print(i)
        exit()

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int,input().split())
li2=[input() for i in range(n)]
ab = []
for i in range(n):
    ab.append( [int(x.strip()) for x in li2[i].split()])
w = (int(h/ab[0][0])+1) * ab[0][1]
dp = [[0] * (w+1) for i in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j < ab[i][1]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i+1][j-ab[i][1]]+ab[i][0])

ans = 0
for i in range(w+1):
    if dp[n][i] >= h:
        print(i)
        exit()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import defaultdict
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba

def run():
    H, N = map(int, sysread().split())
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]

    INF = float('inf')
    dp = [[INF] * (2*H+2) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(2*H+2):
            tmp = j - A[i]
            if tmp >= 0:
                dp[i+1][j] = min([dp[i][j], dp[i+1][tmp] + B[i]])
            elif j == H and tmp < 0:
                dp[i + 1][H] = min(dp[i][H], dp[i + 1][0] + B[i])
            else:
                dp[i+1][j] = dp[i][j]
    ret = min(dp[N][H:])
    print(ret)



if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import defaultdict
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba

def run():
    H, N = map(int, sysread().split())
    AB = []
    for i in range(N):
        a,b = map(int, sysread().split())
        AB.append((a,b))

    INF = float('inf')
    dp = [[INF] * (2*H+2) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(2*H+2):
            tmp = j - AB[i][0]
            if tmp >= 0:
                dp[i+1][j] = min([dp[i][j], dp[i+1][tmp] + AB[i][1]])
            elif j == H and tmp < 0:
                dp[i + 1][H] = min(dp[i][H], dp[i + 1][0] + AB[i][1])
            else:
                dp[i+1][j] = dp[i][j]
    ret = min(dp[N][H:])
    print(ret)



if __name__ == "__main__":
    run()

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

magic = [float("inf")] * (h + 1)
magic[0] = 0

for i in range(n):
    for j in range(0, h + 1):
        if j + a[i] <= h:
            magic[j + a[i]] = min(magic[j + a[i]], magic[j] + b[i])
        else:
            magic[h] = min(magic[h], magic[j] + b[i])

print(magic[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**10 for i in range(h+1)]

dp[h]=0

for i in reversed(range(1,h+1)):
    for j in range(n):
        if i-A[j]>=0:
            dp[i-A[j]]=min(dp[i-A[j]],dp[i]+B[j])
        else:
            dp[0]=min(dp[0],dp[i]+B[j])

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = np.full(Hmax+1, INF, dtype=int)
dp[0] = 0
print(rec_z())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = np.full(Hmax+1, INF, dtype=int)
dp[0] = 0
print(rec_z())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [INF for _ in range(Hmax+1)] 
dp[0] = 0
print(rec_z())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j < a[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i+1][j-a[i]] + b[i])
    return min(dp[N][H:Hmax+1])


H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [[INF for _ in range(Hmax+1)] for _ in range(N+1)] 
dp[0][0] = 0
print(rec_z())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j < a[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i+1][j-a[i]] + b[i])
    return min(dp[N][H:Hmax+1])


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())
Hmax = H + max(a)
INF = 10**9
dp = np.full((N+1,Hmax+1), INF, dtype=int)
dp[0][0] = 0
print(rec_z())

Submission status: Time Limit Exceeded

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

dp = [float('inf')]*(H+1)
dp[0] = 0
for h in range(H+1):
    for n in range(N):
        damage = Alist[n]
        cost = Blist[n]
        first_index = min(h + damage, H)
        dp[first_index] = min(dp[h] + cost, dp[first_index])
        
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, N = map(int, input().split())
    magic = [list(map(int, input().split())) for _ in range((N))]
    dp = [float('inf')] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for dmg, cst in magic:
            next = min(h + dmg, H)
            dp[next] = min(dp[next], dp[h] + cst)
    print(dp[h+1])
main()

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
L = [list(map(int, input().split())) for _ in range((N))]
dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for dmg, cst in L:
        next = min(h + dmg, H)
        dp[next] = min(dp[next], dp[h] + cst)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import defaultdict
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba

def run():
    H, N = map(int, sysread().split())
    AB = list(map(int, read().split()))
    A = [0] + AB[0::2]
    B = [0] + AB[1::2]

    INF = float('inf')
    dp = [[INF] * (H+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(0, N):
        for v in range(H+1):
            dp[i+1][v] = min(dp[i][v], dp[i+1][v])
            do = True
            pre_v = v
            while do:
                next_v = pre_v + A[i+1]
                if next_v >= H:
                    next_v = H
                    do = False
                dp[i+1][next_v] = min(dp[i+1][next_v], dp[i+1][pre_v] + B[i+1])
                pre_v = next_v
    print(dp[N][H])

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    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 = [INF] * 10000100
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for n in range(N):
            dp[i+A[n]] = min(dp[i+A[n]], dp[i] + B[n])
    
    ans = INF
    for i in range(H, 10000100):
        ans = min(ans, dp[i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9

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

dp[0] = 0

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

print(dp[H])

Submission status: Time Limit Exceeded

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

A=[]
B=[]
DP=[0]+[float('Inf')]*(2*10**4)

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

for j in range(10**4):
  for i in range(N):
    DP[j+A[i]]=min(B[i]+DP[j],DP[j+A[i]])

print(min(DP[H:]))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, maxsize

def main():
    input = stdin.readline

    h, n = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    dp = [maxsize] * (h + 1)
    dp[0] = 0
    for i in range(h + 1):
        if dp[i] == maxsize:
            continue
        for x, y in a:
            if i + x < h and dp[i + x] > dp[i] + y:
                dp[i + x] = dp[i] + y
            elif i + x >= h and dp[h] > dp[i] + y:
                dp[h] = dp[i] + y
    print(dp[h])
main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, maxsize

def main():
    input = stdin.readline

    h, n = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    dp = [maxsize] * (h + 1)
    dp[0] = 0
    for i in range(h + 1):
        for x, y in a:
            if i + x < h and dp[i + x] > dp[i] + y:
                dp[i + x] = dp[i] + y
            elif i + x >= h and dp[h] > dp[i] + y:
                dp[h] = dp[i] + y
    print(dp[h])
main()

Submission status: Time Limit Exceeded

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


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    dp = [[0 for h in range(H+1)] for n in range(N+1)] # dp[N][H]はN番目までの魔法を使ってHの敵を倒す最小のMP

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

    for h in range(1, H+1):
        dp[0][h] = float('inf')

    for h in range(H+1):
        for n in range(N):
            dp[n+1][h] = min(dp[n][h], dp[n+1][max(0, h-A[n])]+B[n])
    print(dp[N][H])

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int,input().split())
mahou = []
for i in range(n):
	a,b = map(int,input().split())
	mahou.append((a,b))
dp = [10**18 for _ in range(h+1)]
dp[0] = 0
for i in range(h+1):
	for j, k in mahou:
		if j+i <= h:
			dp[j+i] = min(dp[i]+k, dp[j+i])
		else:
			dp[h] = min(dp[i]+k, dp[h])
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)]
mx=max(a for a,b in ab)
dp=[float('inf')]*(h+1+mx)
dp[0]=0
for i in range(1,h+1+mx):
  dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


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


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


H, N = zz()
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = zz()
# dp = [0]*(H+max(A)+1)  # dp[i]: HPをi減らすのに必要な最低の魔力
dp = np.zeros(H+max(A)+1, np.int32)
arg_min = np.argmin(A)
dp[:min(A)+1] = B[arg_min]

for i in range(min(A)+1, H + max(A)):
    dp[i] = min(dp[i - a] + b for a, b in zip(A, B))

print(min(dp[H:H+max(A)]))
# print((dp[H:H+max(A)]))

Submission status: Time Limit Exceeded

Solution code:
INF=10**30
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=[INF]*(H+10)
dp[0]=0
for i in range(N):
    for j in range(H+1):
        if(j<A[i]):
            dp[j]=min(dp[j],dp[0]+B[i])
        else:
            dp[j]=min(dp[j],dp[j-A[i]]+B[i])
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
h,n,*t = map(int,open(0).read().split())

dp = [0] + [10**8]* h

for a,b in  zip(*[iter(t)]*2):
    for life_point in range(h +1):
        
        original_life = max(0,life_point - a)
#         print(original_life)
        magic_consum = dp[original_life]+ b
#         print(magic_consum)
        dp[life_point] = min(dp[life_point],magic_consum)
#         print(dp)
print(dp[h])

Submission status: Time Limit Exceeded

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

ab = []
ma = 0
for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b])
    ma = max(ma,a)

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

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

print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

ab = []
ma = 0
for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b])
    ma = max(ma,a)

dp = [float('inf')]*(h+ma+1)
dp[0] = 0

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

print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

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

print(dp[n][h])

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int,input().split())
dp = [[float('inf')]*(h+1) for i in range(n+1)]
dp[0][0] = 0

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

print(dp[n][h])

Submission status: Time Limit Exceeded

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

magics = [list(map(int,input().split())) for _ in range(N)]
max_A = max(a for a,b in magics)
DP = [float('inf')]*(H+max_A)
DP[0] = 0
for i in range(1,H+max_A):
    DP[i] = min(DP[i-a] + b for a,b in magics)

ans = min(DP[H:])

print(ans)

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 = [float('inf')]*(H+max(A))
DP[0] = 0
for i in range(H):
    if DP[i] != float('inf'):
        for j in range(N):
            DP[i+A[j]] = min(DP[i+A[j]],DP[i]+B[j])

ans = min(DP[H:])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

    # dp = np.full((N+1,H+1),10 ** 18)
    # dp[0][0] = 0
    dp = [float('inf')]*(H+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            # print(i,j,dp[j],A[i],B[i])
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)], dp[j]+B[i])
            # dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            # dp[i+1][min(j+A[i],H)] = min(dp[i+1][j]+B[i], dp[i+1][min(j+A[i],H)])
            # print(dp)
    print(int(dp[H]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
 
# = map(int,input().split())
 
# = list(map(int,input().split()))
 
# = [list(map(int,input().split())) for _ in range(XXXX)]
from sys import stdin


def main():
    input = stdin.readline
    
    h,n = map(int,input().split())
    
    ab= [list(map(int,input().split())) for _ in range(n)]
    
    dp = [[100000001 for _ in range(h+1)] for _ in range(n+1)]
    #dp[i][j]はi番目のものを選んだ時かつダメージ送料がjだったときの最小MP、
    
    
    for i in range(1,n+1):
        dp[i][0] = 0
        for j in range(h+1):
            a = ab[i-1][0]
            b = ab[i-1][1]
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            if j+a <= h:
                dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
            elif j+a > h:
                dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
 
# = map(int,input().split())
 
# = list(map(int,input().split()))
 
# = [list(map(int,input().split())) for _ in range(XXXX)]
from sys import stdin
input = stdin.readline
 
h,n = map(int,input().split())
 
ab= [list(map(int,input().split())) for _ in range(n)]
 
dp = [[float("inf") for _ in range(h+1)] for _ in range(n+1)]
#dp[i][j]はi番目のものを選んだ時かつダメージ送料がjだったときの最小MP、
 
 
for i in range(1,n+1):
    dp[i][0] = 0
    for j in range(h+1):
        a = ab[i-1][0]
        b = ab[i-1][1]
        dp[i][j] = min(dp[i][j],dp[i-1][j])
        if j+a <= h:
            dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
        elif j+a > h:
            dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

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

#print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

    dp = np.full((N+1,H+1),float('inf'))
    dp[0][0] = 0
    for i in range(N):
        for j in range(H+1):
            # print(i,j)
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][min(j+A[i],H)] = min(dp[i+1][j]+B[i], dp[i+1][min(j+A[i],H)])
            # print(dp)
    print(int(dp[N][H]))


if __name__ == '__main__':
    main()