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 time

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

INF = 10 ** 9

magic = []

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

# t = time.time()

magic.sort(reverse=True, key=lambda x: x[0])

dp = [INF] * (h + 10 ** 4)
dp[0] = 0
c = 0
for a, b in magic:
    for i in range(h):
        if dp[i] != INF:
            tmp = dp[i] + b
            c += 1
            if dp[i + a] > tmp:
                dp[i + a] = tmp

ans = min(dp[h:])

print(ans)
# print(time.time() - t)

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_inf = float("inf")
dp = [f_inf] * (h + max(a))
dp[0] = 0
for i in range(n):
    for j in range(h):
        if dp[j] != f_inf:
            if dp[j + a[i]] > dp[j] + b[i]:
                dp[j + a[i]] = dp[j] + b[i]

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, N = map(int, input().split())
    dp = [10 ** 18] * (H + 1)

    dp[0] = 0

    for i in range(N):
        a, b = map(int, input().split())
        for j in range(H):
            nj = min(j + a, H)  # nj: 次のjのindex, 配列外参照しないようにminをとる
            dp[nj] = min(dp[nj], dp[j] + b)

    print(dp[H])


main()

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

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

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
dp = [10 ** 18] * (H + 1)

dp[0] = 0

for i in range(N):
    a, b = map(int, input().split())
    for j in range(H):
        nj = min(j + a, H)  # nj: 次のjのindex, 配列外参照しないようにminをとる
        dp[nj] = min(dp[nj], dp[j] + b)

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
H,N=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
dp=[10**9+1]*H

for i in range(H):
  for a,b in AB:
    if i-a<0:
      if dp[i]>b:
        dp[i]=b
    else:
      if dp[i]>dp[i-a]+b:
        dp[i]=dp[i-a]+b
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
H,N=map(int, input().split())
AB = [list(map(int,input().split())) for i in range(N)]
dp=[10**8]*(H+1)
dp[0]=0
for i in range(1,H+1):
  for ab in AB:
    dp[i]=min(dp[max(0,i-ab[0])] + ab[1], dp[i])
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import time

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

INF = 10 ** 20


dp = [INF for i in range(h + 10**4)]
dp[0] = 0

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))


que = [0]
cc = [0]
m = 0
c = 0
for i in range(h):
    if dp[i] == INF:
        continue
    for a, b in magic:
        dam = i + a
        if dp[dam] > dp[i] + b:
            dp[dam] = dp[i] + b

ans = min(dp[h:])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import time

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

INF = 10 ** 20


dp = [INF for i in range(h + 10**4)]
dp[0] = 0

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))


que = [0]
cc = [0]
m = 0
c = 0
for i in range(h):

    for a, b in magic:
        dam = i + a
        if dp[dam] > dp[i] + b:
            dp[dam] = dp[i] + b

ans = min(dp[h:])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
h, n = map(int, input().split())
a = [0]*n
b = [0]*n
ma = 0
for i in range(n):
    a[i], b[i] = map(int, input().split())
    ma = max(a[i], ma)

H = h + ma + 1
dp = [sys.maxsize]*H

dp[0] = 0
ans = sys.maxsize
for i in range(1, H):
    for j in range(n):
        dp[i] = min(dp[max(i-a[j], 0)]+b[j], dp[i])
    if i >= h:
        ans = min(ans, dp[i])
print(ans)

Submission status: Time Limit Exceeded

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

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

H = h+max(a)
dp = [sys.maxsize]*H

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

Submission status: Time Limit Exceeded

Solution code:
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = map(int, open(0).read().split())
    dp = [INF] * (H + 10001)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            dp[i + a] = min(dp[i + a], dp[i] + b)
    print(min(dp[H:]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = map(int, open(0).read().split())
    dp = [INF] * (H + 1)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            if i + a < H and dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
            elif i + a >= H and dp[i] + b < dp[H]:
                dp[H] = dp[i] + b
    print(dp[H])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30
    
    H, N, *AB = map(int, open(0).read().split())
    dp = [INF] * (H + 1)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            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])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if i not in dp:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            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])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if i not in dp:
                continue
            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])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H, N = [int(i) for i in input().split()]
An = []
Bn = []
#Rn = []
for n in range(N):
  a, b = [int(i) for i in input().split()]
  An.append(a)
  Bn.append(b)
#  Rn.append(b/a)

maxA = max(An)
dp = [[1000000000 for _ in range(H+1 )] for _ in range(N+1)]
dp[0][0] = 0
for n in range(N):
  dp[n][0] = 0
  a, b = An[n], Bn[n]
  for h in range(1, H+1):
    if h == H:
      dp[n+1][h] = min(min(dp[n][h-a:]) + b, dp[n][h], 
                       min(dp[n+1][h-a:]) + b)
    elif h >= a:
      dp[n+1][h] = min(dp[n][h-a] + b, dp[n][h], dp[n+1][h-a] + b)
    else:
      dp[n+1][h] = dp[n][h]
print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
import math

#Input
H, N = map(int, input().split())
lstV = list()
lstC = list()
for i in range(N):
    value, cost = map(int, input().split())
    lstV.append(value)
    lstC.append(cost)

#DPMap
inf = 2**31 - 1
dp = list([inf]*(H + max(lstV)))
dp[0] = 0
for i in range(0,len(dp)):
    if dp[i] != inf:
        for j in range(0,len(lstV)):
            value = lstV[j]
            cost = lstC[j]
            if i + value <= len(dp) - 1:
                dp[i + value] = min(dp[i + value], dp[i] + cost)
print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
H, N = [int(i) for i in input().split()]
An = []
Bn = []
#Rn = []
for n in range(N):
  a, b = [int(i) for i in input().split()]
  An.append(a)
  Bn.append(b)
#  Rn.append(b/a)

maxA = max(An)
dp = [[1000000000 for _ in range(H+1 + maxA)] for _ in range(N+1)]
dp[0][0] = 0
for n in range(N):
  dp[n][0] = 0
  a, b = An[n], Bn[n]
  for h in range(1, H+1+maxA):
    if h >= a:
      dp[n+1][h] = min(dp[n][h-a] + b, dp[n][h], dp[n+1][h-a] + b)
    else:
      dp[n+1][h] = dp[n][h]
print(min(dp[N][H:]))

Submission status: Time Limit Exceeded

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

h, n = map(int, input().split())
a = map(int, read().split())
ab = zip(a, a)

INF = 10 ** 18
dp = [INF] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        if dp[i + a] > dp[i] + b:
            dp[i + a] = dp[i] + b
print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

h, n = map(int, input().split())
a = map(int, read().split())
ab = zip(a, a)

dp = [10 ** 18] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        if dp[i + a] > dp[i] + b:
            dp[i + a] = dp[i] + b
print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

h, n = map(int, input().split())
a = map(int, read().split())
ab = zip(a, a)

dp = [10 ** 20] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        if dp[i + a] > dp[i] + b:
            dp[i + a] = dp[i] + b
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, N = map(int, input().split())
array = [list(map(int, input().split())) for i in range(N)]

d = [i[0] for i in array]
m = [i[1] for i in array]
dp = [[np.inf for i in range(H+1)] for j in range(N+1)]

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

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

Submission status: Time Limit Exceeded

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

h, n = map(int, input().split())
ab = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [10 ** 20] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        if dp[i + a] > dp[i] + b:
            dp[i + a] = dp[i] + b
print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

dp = [10 ** 20] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        if dp[i + a] > dp[i] + b:
            dp[i + a] = dp[i] + b
print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

dp = [10 ** 18] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

dp = [10 ** 20] * 10 ** 5
dp[0] = 0
for a, b in ab:
    for i in range(h):
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
import math
H,N=map(int,input().split())
A=[0 for i in range(N)]
B=[0 for i in range(N)]
dp=[[0 for j in range(H)] for i in range(N)]
for i in range(N):
    A[i],B[i]=map(int,input().split())

for i in range(N):
    for j in range(H):
        if i==0:
            dp[i][j]=B[i]*math.ceil((j+1)/A[i])
        elif j+1<=A[i]:
            dp[i][j]=min(dp[i-1][j],B[i])
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-A[i]]+B[i])

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

Submission status: Time Limit Exceeded

Solution code:
import math
H,N=map(int,input().split())
A=[]
B=[]
dp=[[0 for j in range(H)] for i in range(N)]
for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

for i in range(N):
    for j in range(H):
        if i==0:
            dp[i][j]=B[i]*math.ceil((j+1)/A[i])
        elif j+1<=A[i]:
            dp[i][j]=min(dp[i-1][j],B[i])
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-A[i]]+B[i])

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

Submission status: Time Limit Exceeded

Solution code:
'''input
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
'''
from sys import stdin
input = stdin.readline
import math
import sys

sys.setrecursionlimit(10 ** 4)


def brute(arr, h, dp):
	if h <= 0:
		return 0
	if dp[h] != -1:
		return dp[h]

	first = float('inf')
	for i in range(len(arr)):
		first = min(first, arr[i][1] + brute(arr, h - arr[i][0], dp))
		
	dp[h] = first
	return first

	
# main starts
h, n = list(map(int, input().split()))
arr = []

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

dp = [-1] * (h + 1)
print(brute(arr, h, dp))

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
a = []
b = []
for _ in range(n):
  ai, bi = map(int, input().split())
  a.append(ai)
  b.append(bi)
dp = [0] * (h+1)
for c in range(1, h+1):
  dp[c] = min([dp[max(0, c-a[i])] + b[i] for i in range(n)])
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
ab = []
for _ in range(n):
  a, b = map(int, input().split())
  ab.append((a, b))
dp = [0] * (h+1)
for c in range(1, h+1):
  dp[c] = min([dp[max(0, c-a)] + b for a, b in ab])
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)]
dp = [float('inf')] * (h+1)

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:

     

import math
import numpy as np


H,N = map(int,input().split())
Damage = []
Cost = []


DP = [0] + [pow(10,9)] * (H+1)



for i in range(N):
    a,b = map(int,input().split())
    Damage.append(a)
    Cost.append(b)
    
#print(DP)

damage = np.array(Damage)
cost = np.array(Cost)
dp = np.array(DP)




# DP[i] = best magic points to do i damage

for i in range(1,len(dp)):
    for spell in range(N):
        dp[i] = min(dp[i],dp[max(0,i-damage[spell])]+cost[spell])




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)]
dp = [float('inf')] * h

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import math


H,N = map(int,input().split())
Damage = []
Cost = []


DP = [0] + [pow(10,9)] * (H+1)



for i in range(N):
    a,b = map(int,input().split())
    Damage.append(a)
    Cost.append(b)
    
#print(DP)


# DP[i] = best magic points to do i damage

for i in range(1,len(DP)):
    for spell in range(N):
        DP[i] = min(DP[i],DP[max(0,i-Damage[spell])]+Cost[spell])




print (DP[H])

Submission status: Time Limit Exceeded

Solution code:
inf = 10**9
H, N = map(int, input().split())
AB = []
for n in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(reverse=True, key=lambda x: x[0])
dp = [inf] * (H + 10 ** 4)
dp[0] = 0
for a, b in AB:
    for h in range(H):
        if dp[h] != inf:
            tmp = dp[h] + b
            if tmp < dp[h + a]:
                dp[h + a] = tmp
print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
inf = 10**9
H, N = map(int, input().split())
AB = []
for n in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(reverse=True, key=lambda x: x[0])
dp = [inf] * (H + 10 ** 4)
dp[0] = 0
for a, b in AB:
    for h in range(H):
        if dp[h] != inf:
            tmp = dp[h] + b
            if tmp < dp[h + a]:
                dp[h + a] = tmp
print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
inf = 10**10
H, N = map(int, input().split())
A = []
B = []
for n in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dp = [inf] * (H + 10 ** 4)
dp[0] = 0
for n in range(N):
    for h in range(H):
        if dp[h] == inf:
            continue
        dp[h + A[n]] = min(dp[h + A[n]], dp[h] + B[n])
print(min(dp[H:]))

Submission status: Time Limit Exceeded

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

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

dp[0]=0
for _ in range(n):
    a, b = map(int, input().strip().split())
    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 = map(int, input().strip().split())
AB = [list(map(int, input().split())) for i in range(n)]

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

dp[0]=0
for ab in AB:
    a=ab[0]
    b=ab[1]
    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 = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        min_bsum = min(min_bsum,bsum[max(0,i-a[atk])]+b[atk])
    bsum.append(min_bsum)
 
#指定のHのコストを表示
print(bsum[h])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

dp[0]=0
for ab in AB:
    a=ab[0]
    b=ab[1]
    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:
import numpy as np

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum = np.zeros(h+1)
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        min_bsum = min(min_bsum,bsum[max(0,i-a[atk])]+b[atk])
    bsum[i] = min_bsum

#指定のHのコストを表示
print(int(bsum[h]))

Submission status: Time Limit Exceeded

Solution code:
def DP():
  H,N,*T = map(int,open(0).read().split())
  
  #dpテーブルの設定と初期化
  dp = [0] + [10 ** 9] * H
  
  #各魔法について
  for d,c in zip(*[iter(T)] * 2):
    #d,cはそれぞれ魔法ダメージと魔法のコスト
    #dpテーブルの各HPについて
    for j in range(H + 1):
      k = max(j - d,0)
      #ダメージjを与える時のコストについて、
      #魔法iを新たに使った場合と、既存の最小コストを比較し更新する
      l = dp[k] + c
      dp[j] = min(l,dp[j])
  
  print(dp[-1])
  
DP()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum = np.zeros(10**4+1)
bsum[0] = 0
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        min_bsum = min(min_bsum,bsum[max(0,i-a[atk])]+b[atk])
    bsum[i] = min_bsum

#指定のHのコストを表示
print(int(bsum[h]))

Submission status: Time Limit Exceeded

Solution code:
def DP():
  H,N = map(int,input().split())
  
  #dpテーブルの設定と初期化
  dp = [0] + [10 ** 9] * H
  
  #各魔法について
  for i in range(N):
    #d,cはそれぞれ魔法ダメージと魔法のコスト
    d,c = map(int,input().split())
    #dpテーブルの各HPについて
    for j in range(H + 1):
      k = max(j - d,0)
      #ダメージjを与える時のコストについて、
      #魔法iを新たに使った場合と、既存の最小コストを比較し更新する
      l = dp[k] + c
      dp[j] = min(dp[j],l)
 
  print(dp[-1])
  
DP()

Submission status: Time Limit Exceeded

Solution code:
H,N,*T = map(int,open(0).read().split())

#dpテーブルの設定と初期化
dp = [0] + [10 ** 9] * H

#各魔法について
for d,c in zip(*[iter(T)] * 2):
  #d,cはそれぞれ魔法ダメージと魔法のコスト
  #dpテーブルの各HPについて
  for j in range(H + 1):
    k = max(j - d,0)
    #ダメージjを与える時のコストについて、
    #魔法iを新たに使った場合と、既存の最小コストを比較し更新する
    l = dp[k] + c
    dp[j] = min(l,dp[j])

print(dp[-1])

Submission status: Time Limit Exceeded

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

#dpテーブルの設定と初期化
dp = [0] + [10 ** 9] * H

#各魔法について
for i in range(N):
  #d,cはそれぞれ魔法ダメージと魔法のコスト
  d,c = map(int,input().split())
  #dpテーブルの各HPについて
  for j in range(H + 1):
    k = j - d
    if j - d < 0:
      k = 0
    #ダメージjを与える時のコストについて、
    #魔法iを新たに使った場合と、既存の最小コストを比較し更新する
    l = dp[k] + c
    if l < dp[j]:
      dp[j] = l

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

#dpテーブルの設定と初期化
dp = [0] + [10 ** 9] * H

#各魔法について
for i in range(N):
  #d,cはそれぞれ魔法ダメージと魔法のコスト
  d,c = map(int,input().split())
  #dpテーブルの各HPについて
  for j in range(H + 1):
    k = max(j - d,0)
    #ダメージjを与える時のコストについて、
    #魔法iを新たに使った場合と、既存の最小コストを比較し更新する
    l = dp[k] + c
    dp[j] = min(dp[j],l)

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4
    dp = [INF] * MAX_LEN
    dp[0] = 0
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4
    dp = [0] + [INF] * MAX_LEN
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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)
inf=10**10
f=h+max(a)+1
#dp[i][j]=i番目までの魔法を使えるとき、体力をj減らす最小魔力
dp=[f*[inf]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  dp[i][0]=0
  for j in range(f):
    dp[i][j]=dp[i-1][j]
    if j-a[i-1]>=0:dp[i][j]=min(dp[i][j],dp[i][j-a[i-1]]+b[i-1])
print(min(dp[-1][h:]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 + 1
    dp = [0] + [INF] * MAX_LEN
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h+1):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    ans = min(dp[h:])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])

Submission status: Time Limit Exceeded

Solution code:
inf = 10**10
H, N = map(int, input().split())
A = []
B = []
for n in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dp = [[0 for h in range(H+1)] for n in range(N+1)]
# dp[n][h]は0~n-1の魔法で体力hを削るのに使う魔力
dp[0] = [0] + [inf for h in range(1, H+1)]
for n in range(1, N+1):
    for h in range(H+1):
        dp[n][h] = min(dp[n - 1][h], dp[n][max(0, h - A[n - 1])] + B[n - 1])
print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 + 1
    dp = [0] + [INF] * MAX_LEN
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h+1):
            tmp = dp[j] + w
            if dp[j] != INF and tmp < dp[j+v]:
                dp[j+v] = tmp
    ans = min(dp[h:])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,10**4+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10
 
h, n = [int(item) for item in input().split()]
MAX_LEN = h + 10**4 + 1
dp = [INF] * MAX_LEN
dp[0] = 0
for i in range(n):
    v, w = map(int, input().split())
    for j in range(h+1):
        if dp[j] != INF and dp[j] + w < dp[j+v]:
            dp[j+v] = dp[j] + w
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)
AB = zip(A,B)
INF = 10**10
dp = [INF]*(20000)
dp[0]=0
for a,b in AB:
    for i in range(h):
        if dp[i+a]>dp[i]+b:
            dp[i+a]=dp[i]+b

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = np.full(h + 10001, INF, dtype=np.int64)
dp[0] = 0
for line in sys.stdin:
    a, b = map(int, line.split())
    for s in range(0, h, a):
        dp[s + a:h + a] = np.minimum(dp[s + a:h + a], dp[s:h] + b)
print(dp[h:].min())

Submission status: Time Limit Exceeded

Solution code:
'''input
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
'''
from sys import stdin
input = stdin.readline
import math
import sys, resource
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)


def mp(first, second):
	return str(first) + ' '  + str(second)


def brute(arr, h, dp):
	if h <= 0:
		return 0
	if h in dp:
		return dp[h]

	first = float('inf')
	for i in range(len(arr)):
		first = min(first, arr[i][1] + brute(arr, h - arr[i][0], dp))
		
	dp[h] = first
	return first

	
# main starts
h, n = list(map(int, input().split()))
arr = []

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

dp = dict()
print(brute(arr, h, dp))

Submission status: Time Limit Exceeded

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

if h == 1:
    print(min(b))
else:
    dp = [0]*h
    dp[0] = min(b)
    for i in range(2,h+1):
        c = [0]*n
        for j in range(n):
            if i > a[j]:
                c[j] = b[j] + dp[i-a[j]-1]
            else:
                c[j] = b[j]
        dp[i-1] = min(c)
    print(dp[h-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

lists=[]
for i in range(n):
    a,b=map(int,input().split())
    lists.append([a,b])
    
    
#dic[x]=y モンスターの体力をｘ減らすために必要な魔力
minimum=[10**9 for i in range(20001)]
#minimum[k]=ダメージｋを与えるために最小の魔力
minimum[0]=0
for i in range(1,20001):
    for j in range(n):
        if i>=lists[j][0]:
            minimum[i]=min(minimum[i-lists[j][0]]+lists[j][1],minimum[i])
        else:
            minimum[i]=minimum[i]
ans=10**8
for k in range(h,20001):
    ans=min(ans,minimum[k])
print(ans)