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 math

H,N=map(int,input().split())
A_list=[]
B_list=[]
for i in range(N):
    A,B=map(int,input().split())
    A_list.append(A)
    B_list.append(B)

amax=max(A_list)

inf=float('inf')
dp=[0]+[inf]*(H+amax)

for i in range(N):
    A=A_list[i]
    B=B_list[i]
    if A > H and B<dp[-1]:
        dp[-1]=B
        continue

    for j in range(A,1+H):
        if dp[j-A]+B<dp[j]:
            dp[j]=dp[j-A]+B
    
    for j in range(H-A,1+H):
        if dp[j] +B < dp[-1]:
            dp[-1]=dp[j]+B

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import math

H,N=map(int,input().split())
A_list=[]
B_list=[]
for i in range(N):
    A,B=map(int,input().split())
    A_list.append(A)
    B_list.append(B)

amax=max(A_list)

inf=float('inf')
dp=[0]+[inf]*(H+amax)

for i in range(N):
    A=A_list[i]
    B=B_list[i]
    if A > H and B<dp[-1]:
        dp[-1]=B
        continue

    for j in range(A,1+H):
        if dp[j-A]+B<dp[j]:
            dp[j]=dp[j-A]+B
    
    minA=min(dp[H-A:])+B
    if minA < dp[-1]:
        dp[-1]=minA

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import math

H,N=map(int,input().split())
A_list=[]
B_list=[]
for i in range(N):
    A,B=map(int,input().split())
    A_list.append(A)
    B_list.append(B)

amax=max(A_list)

inf=float('inf')
dp=[0]+[inf]*(H+amax)

for i in range(N):
    A=A_list[i]
    B=B_list[i]
    for j in range(A,1+H+amax):
        if dp[j-A]+B<dp[j]:
            dp[j]=dp[j-A]+B

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
import math
import copy

def main():
    H,N=map(int,input().split())

    #inf=float('inf')
    dp=[0]+[1e8]*H

    for i in range(N):
        A,B=map(int,input().split())
        if A>=H:
            dp[-1]=min(B,dp[-1])
        else:
            for j in range(A,H+1):
                dp[j]=min(dp[j-A]+B,dp[j])

                if j > H-A:
                    dp[-1]=min(dp[-1],dp[j]+B)


    print(dp[-1])

main()

Submission status: Time Limit Exceeded

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

#inf=float('inf')
dp=[0]+[1e8]*H

for i in range(N):
    A,B=map(int,input().split())
    if A>=H:
        dp[-1]=min(B,dp[-1])
    else:
        for j in range(A,H+1):
            dp[j]=min(dp[j-A]+B,dp[j])

            if j > H-A:
                dp[-1]=min(dp[-1],dp[j]+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)
inf=float('inf')
dp = [[inf] * (h + 1) for i in range(n + 1)]
dp[0][0]=0
for i in range(n):
    for j in range(h + 1):
        if j < A[i]:
            dp[i + 1][j] = min(dp[i][j], B[i])
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - A[i]] + B[i])
print(dp[n][h])

Submission status: Time Limit Exceeded

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

#inf=float('inf')
dp=[0]+[int(1e8)]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=copy.deepcopy(dp)
    for j in range(A,H+1):
        ndp[j]=min(ndp[j],ndp[j-A]+B,dp[j])

        if j > H-A:
            ndp[-1]=min(ndp[-1],ndp[j]+B)

    if A>=H:
        ndp[-1]=min(B,dp[-1])

    dp=ndp

print(dp[-1])

Submission status: Time Limit Exceeded

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

damage = [0] * n
mp     = [0] * n
for i in range(n):
    damage[i], mp[i] = list(map(int, input().split()))


inf = 9999999999
dp = [inf] * (h+1)
dp[0] = 0

for i in range(n):
    for j in range(h):
        nj = min(j + damage[i], h)
        dp[nj] = min(dp[nj], dp[j]+mp[i])
print(dp[-1])

Submission status: Time Limit Exceeded

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

def main():
    H, N = map(int, input().split())
    AB = [list(map(int, input().split())) for i in range(N)]
    
    dp = [float('inf') for i in range(H+1)]
    dp[-1] = 0
    
    for A, B in AB:
        for i in range(H, -1, -1):
            idx = max(0, i-A)
            dp[idx] = min(dp[idx], dp[i]+B)
    print(dp[0])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

for _ in range(N):
    a, b = map(int, input().split())
    for i in range(1, H // a + 2):
        if b * i < magics[a * i] or magics[a * i] == 0:
            magics[a * i] = b * i

M = len(magics)

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

for h in range(H + 1):
    for a, b in magics.items():
        dp[h] = min(dp[h], dp[max(h - a, 0)] + b)

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
import sys


def resolve():
    H, N = map(int, sys.stdin.readline().split())
    m = map(int, sys.stdin.read().split())
    AB = zip(m, m)
    INF = 10**20
    dp = [INF]*(H+10**4)
    dp[0] = 0
    for a, b in AB:
        for j in range(H+10**4):
            dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
    return min(dp[H:])


if __name__ == '__main__':
    print(resolve())

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 = [0] + [-1] * h
INF = 10**18
for hp in range(1, h+1):
    ret = INF
    for i in range(n):
        if hp - a[i] >= 0:
            ret = min(ret, dp[hp-a[i]] + b[i])
        else:
            ret = min(ret, b[i])
    dp[hp] = ret
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
lis = []
for n in range(N):
    a, b = map(int, input().split())
    lis.append((a, b))
#print(lis)
dp = [0] * (H+1)
for h in range(1, H+1):
    dp[h] = min([lis[n][1] + dp[max(h-(lis[n][0]), 0)] for n in range(N)])
#print(dp)
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def main():
    H, N = LI()
    A, B = [], []
    for _ in range(N):
        a, b = LI()
        A.append(a)
        B.append(b)
    dp = [[0 for _ in range(10001)] for __ in range(1001)]
    for col in range(1, 10001):
        dp[0][col] = inf
    for i in range(N):
        for j in range(H+1):
            if j - A[i] >= 0:
                dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]] + B[i])
            else:
                dp[i+1][j] = min(dp[i][j], B[i])
    print(dp[N][H])
main()

Submission status: Time Limit Exceeded

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


ab = []
for i in range(n):
    ab.append([int(i) for i in input().split()])
ab.sort()

dp = []
for i in range(h + ab[n-1][0]):
    dp.append(pow(2, 31) - 1)
dp[0] = 0

for i in range(1, len(dp)):
    tmp = dp[i]
    for j in range(n):
        #print(j-ab[j][0])
        tmp = min(tmp, dp[max(0, i-ab[j][0])]+ab[j][1])
    dp[i] = tmp

#print(dp)
print(min(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)
inf = 1000000000
fin = max(a)+h 
dp = [inf]*(fin)
dp[0] = 0
for i in range(n):
  x = [a[i], b[i]]
  for j in range(fin):
    if dp[j] != inf:
      if j+x[0] < fin:
        dp[j+x[0]] = min(dp[j+x[0]], dp[j]+x[1])
print(min(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)
inf = 1000000000
fin = max(a)+h 
dp = [inf]*(fin)
dp[0] = 0
for i in range(n):
  x = [a[i], b[i]]
  for j in range(fin):
    if j+x[0] < fin:
      dp[j+x[0]] = min(dp[j+x[0]], dp[j]+x[1])
print(min(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)
inf = 1000000000
ma = max(a)
dp = [inf]*(h+ma)
dp[0] = 0
for i in range(n):
  _a = a[i]
  _b = b[i]
  for j in range(h+ma):
    if j+_a < h+ma:
      dp[j+_a] = min(dp[j+_a], dp[j]+_b)
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, N = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
dp = [[float("inf") for j in range(H+1)] for i in range(N+1)]
for i in range(N):
    for j in range(H+1):
        if j <= A[i]:
            dp[i+1][j] = min(dp[i][j], B[i])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]] + B[i])
print(dp[N][H])

Submission status: Time Limit Exceeded

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

mahou = []

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

#syouhi = [0] * (h+1)
syouhi = [100000000]*(h+1)

#print(syouhi)

syouhi[0] = 0

#syouhi[0][0] = mahou[0][1]
#syouhi[1][0] = mahou[0][1]
#syouhi[0][1] = min(mahou[0][1], mahou[1][1])


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

#print(syouhi)

print(syouhi[h])

Submission status: Time Limit Exceeded

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

mahou = []

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

#syouhi = [0] * (h+1)
syouhi = [[100000000]*(h+1) for i in range(n+1)]

#print(syouhi)

for i in range(n+1) :
    syouhi[i][0] = 0

#syouhi[0][0] = mahou[0][1]
#syouhi[1][0] = mahou[0][1]
#syouhi[0][1] = min(mahou[0][1], mahou[1][1])


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

#print(syouhi)

print(syouhi[n][h])

Submission status: Time Limit Exceeded

Solution code:
H, N = (int(i) for i in input().split())
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = (int(j) for j in input().split())
A_max = max(A)

DP = [0]*(H+A_max)
for i in range(1, H+A_max):
    dp = float('inf')
    for a, b in zip(A,B):
        if i-a>=0:
            dp = min(dp, DP[i-a] + b)
    DP[i] = dp
print(min(DP[H:]))

Submission status: Time Limit Exceeded

Solution code:
H, N = (int(i) for i in input().split())
A = []
B = []
for i in range(N):
    a, b = (int(j) for j in input().split())
    A.append(a)
    B.append(b)
A_max = max(A)

DP = [0]
for i in range(1, H+A_max):
    dp = float('inf')
    for a, b in zip(A,B):
        if i-a>=0:
            dp = min(dp, DP[i-a] + b)
    DP.append(dp)
print(min(DP[H:]))

Submission status: Time Limit Exceeded

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

max_attack=max(at[0] for at in attack)

dp = [0]*(h+max_attack)
for i in range(1,h+max_attack):
    at=[]
    for a,b in attack:
        at.append(dp[i-a]+b)
    dp[i]=min(at)
print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

def main():
    HP,n = map(int,input().split())
    s = [tuple(map(int,input().split())) for i in range(n)]

    #dp[damage] := モンスターにdamageを与える最小コスト
    dp = [float('inf')]*(HP+1) #0~HP
    dp[0] = 0
    for hp in range(HP):
        for damage, cost in s:
            next_idx = min(hp+damage, HP)
            dp[next_idx] = min(dp[next_idx], dp[hp]+cost)
    print(dp[-1])

if __name__ == '__main__':
    main()

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)

G = [0]*(H+1)

for i in range(1,N+1):
    for j in range(1,H+1):
        if i == 1:
            if j-A[i-1]<0:
                G[j] = B[i-1]
            else:
                G[j] = G[j-A[i-1]]+B[i-1]
        elif j-A[i-1]<0:
            G[j] = min(G[j], B[i-1])
        else:
            G[j] = min(G[j], G[j-A[i-1]]+B[i-1])
        
print(G[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)

G = [0]*(H+1)
G_old = [1000000000]*(H+1)

for i in range(1,N+1):
    for j in range(1,H+1):
        if j-A[i-1]<0:
            G[j] = min(G_old[j], B[i-1])
        else:
            G[j] = min(G_old[j], G[j-A[i-1]]+B[i-1])
        G_old[j] = G[j]

print(G[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)

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

for i in range(H+1):
    G[0][i] = 10**9

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

print(G[N][H])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

A = np.zeros(N, dtype = int)
B = np.zeros(N, dtype = int)

for i in range(N):
    A[i],B[i] = map(int,input().split())
    
dp = np.full(H+1, np.inf)
dp[0] = 0
for i in range(1,H+1):
    dp[i] = min([dp[max(i-A[j],0)] + B[j] for j in range(N)])
            
print(int(dp[H]))

Submission status: Time Limit Exceeded

Solution code:
import sys
MAX_INT = sys.maxsize # 大きい値

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

# print(AB)
dp = [ [MAX_INT]*(H+1) for _ in range(N+1) ]

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

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

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
dp = [float('inf')]*(2*(10**4)+1)
dp[0] = 0
l = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
  for j in range(h):
    dp[j+l[i][0]] = min(dp[j+l[i][0]], dp[j]+l[i][1])
    
print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

# 個数制限なしナップサック
# i番目までの魔法を使ったときにHダメージを実現できるときの最小の魔力
dp = [[float('inf')]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H+1):
        # i番目の魔法を使わない時
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # i番目の魔法を使う時
        dp[i+1][min(H, j+A[i])] = min(dp[i][j]+B[i], dp[i+1][j]+B[i], dp[i+1][min(j+A[i], H)])

print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [0] + [INF] * H

for a, b in zip(*[iter(AB)] * 2):
    for i in range(H + 1):
        idx = i + a if i + a < H else H
        dp[idx] = dp[idx] if dp[idx] < dp[i] + b else dp[i] + b

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [0] + [INF] * H

for a, b in zip(*[iter(AB)] * 2):
    for i in range(H + 1):
        idx = min(i + a, H)
        dp[idx] = min(dp[idx], dp[i] + b)

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [0] + [INF] * (H + max(AB[::2]))

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [0] * (H + 10 ** 4 + 10)

for i in range(1, len(dp)):
    dp[i] = min(dp[i - a] + b for a, b in zip(*[iter(AB)] * 2))

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [INF] * (H + 10 ** 4 + 10)
dp[0] = 0

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
# DPで解く
# dp[i] := iまでダメージを与えたときに消費する最小の魔力
import math
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)
max_A=max(A)
DP=[10000000000000000000000 for i in range(H+max_A+1)]
DP[0]=0
for i in range(H):
    for j,b in enumerate(B):
        DP[i+A[j]] = min(DP[i]+b, DP[i+A[j]])

print(min(DP[H:H+max_A+1]))

Submission status: Time Limit Exceeded

Solution code:
# http://drken1215.hatenablog.com/entry/2020/01/26/225000

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):
    dp[min(j+a, H)] = min(dp[min(j+a, H)], dp[j] + b)


print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
inf = 10 ** 18

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, _ in ab)
dp = [inf for _ in range(h + max_a)]
dp[0] = 0
for i in range(1, h + max_a):
    min_dp = inf
    for a, b in ab:
        if 0 > i - a:
            continue
        min_dp = min(min_dp, dp[i-a] + b)
    dp[i] = min_dp
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
# Date: 2020-01-08
# Author: lee215
get = lambda: int(input().strip())
getl = lambda: input().strip()
gets = lambda: list(map(int, input().strip().split()))
getss = lambda n: [gets() for _ in range(n)]

H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur // a0 * b0
    cur += a0


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

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
# Date: 2020-01-08
# Author: lee215

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]

H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur / a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in xrange(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print min(dp[H:])

Submission status: Time Limit Exceeded

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

mahou = []

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

syouhi = [0] * (h+1)

for i in range(1,h+1) :
    min = 100000000
    for j in range(n) :
        if i < mahou[j][0] :
            if min > syouhi[0] + mahou[j][1] :
                min = syouhi[0] + mahou[j][1]

        else :
            if min > syouhi[i-mahou[j][0]] + mahou[j][1] :
                min = syouhi[i-mahou[j][0]] + mahou[j][1]

    syouhi[i] = min

#print(syouhi)

print(syouhi[h])

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]"):
    hmax = H + max(A)
    cost = [0] * hmax
    intmax = 99999
    magics = [(a, b) for a, b in zip(A,B)]
    for i in range(1, hmax):
        for a, b in magics:
            if i >= a:
                cost[i] = min(cost[i-a]+b, cost[i]) if cost[i] > 0 else cost[i-a]+b
            else:
                cost[i] = min(b, cost[i]) if cost[i] > 0 else b
    #print(cost)
    print(min(cost[H:]))

def solve_dijkstra(H: int, N: int, A: "List[int]", B: "List[int]"):
    nodes = {0: 0}
    fixed = 0
    unfixed = set()
    while True:
        cost = nodes[fixed]
        for a, b in zip(A,B):
            new_node = fixed + a
            last = nodes.get(new_node, 999999999)
            new_cost = cost + b
            if last > new_cost:
                nodes[new_node] = new_cost
                unfixed.add(new_node)
        fixed = min(unfixed)
        if fixed >= H:
            break
        unfixed.remove(fixed)
    print(min([v for k, v in nodes.items() if k >= H]))

# Generated by 1.1.6 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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2, floor
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
temp = []
for i in range(N):
	temp.append(LIST())
temp = [list(x) for x in zip(*temp)]
A, B = temp[0], temp[1]

DP = [[INF]*(H + max(A) + 1) for _ in range(N + 1)]

DP[0][0] = 0

a = max(A)

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

print(min(DP[N][H:H + max(A) + 1]))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2, floor
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
temp = []
for i in range(N):
	temp.append(LIST())
temp = [list(x) for x in zip(*temp)]
A, B = temp[0], temp[1]

DP = [[INF]*(H + max(A) + 1) for _ in range(N + 1)]

DP[0][0] = 0

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

print(min(DP[N][H:H + max(A) + 1]))

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]"):
    nodes = {0: 0}
    fixed = 0
    unfixed = set()
    while True:
        cost = nodes[fixed]
        for a, b in zip(A,B):
            new_node = fixed + a
            last = nodes.get(new_node, 999999999)
            new_cost = cost + b
            if last > new_cost:
                nodes[new_node] = new_cost
                unfixed.add(new_node)
        fixed = min(unfixed)
        if fixed >= H:
            break
        unfixed.remove(fixed)
    print(min([v for k, v in nodes.items() if k >= H]))

# Generated by 1.1.6 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:
def solve():
    H,N = map(int, input().split())
    # Aが消費HP, Bが消費MP
    ABs = [list(map(int, input().split())) for _ in range(N)]
    dp_table = [[0]*(H+1) for _ in range(N+1)]
    # dp_table[i][j] : i番目の魔法から消化HPがj以上となる、MPの最小値
    for j in range(1,H+1): dp_table[0][j] = 10**9
    for i in range(N):
        for j in range(H+1):
            if j-ABs[i][0]<0:
                dp_table[i+1][j] = min(dp_table[i][j], ABs[i][1])
            else:
                dp_table[i+1][j] = min(dp_table[i][j], dp_table[i+1][j-ABs[i][0]]+ABs[i][1])
                
    print(dp_table[N][H])
    
solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    dp[0] = 0
    for i in range(1,H+maxA):
        dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp = [0]*(H+1)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin


## This code doesn't pass the test
# def get_result(data):
#     H, N = data[0]
#     A_and_B = np.array(data[1:])
#     calc_efficient = np.array(list(map(lambda x: float(x[0] / x[1]), A_and_B)))
#     sorted_index = np.argsort(-calc_efficient)

#     cost = 0
#     remainder_H = H
#     for i in sorted_index:
#         A, B = A_and_B[i]
#         quotient = remainder_H // A
#         if quotient > 0:
#             cost += B * quotient
#             remainder_H = remainder_H - A * quotient
#         else:
#             if remainder_H > 0:
#                 continue
#             else:
#                 break

#     return cost

## 答え (DP, ナップザック問題の典型らしい)
# 自分の解法は典型的なハマり方をしたっぽい

def get_result(data):
    # 初期化
    H, N = data[0]
    A_and_B = np.array(data[1:])
    A = A_and_B[:, 0].reshape(-1)
    B = A_and_B[:, 1].reshape(-1)

    # 最小化問題だから無限で初期化
    # DP[j] = Aの和が j の時の最小コスト (魔力)
    # 計算量は、O(NH)なのでHが少なくなるようにテーブルは作る
    inf = float("inf")
    # N × H (制約条件) のテーブルを作成
    dp =[inf for j in range(H+1)]
    # 初期値
    dp[0] = 0

    # DP (コードはなんとなく理解できた)
    for i in range(H):
        for j in range(N):
            # 魔力1つずつについてloopさせる
            if (i+1) - A[j] < 0:
                dp[i+1] = min(dp[i+1], dp[0] + B[j])
            else:
                dp[i+1] = min(dp[i+1], dp[i+1-A[j]] + B[j])

    return dp[H]

if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

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')]*(h+1)
dp[0]=0
for a,b in AB:
  for i in range(h):
    if i+a>=h:
      dp[h]=min(dp[h],dp[i]+b)
    else:
      dp[i+a]=min(dp[i+a],dp[i]+b)
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
H,N=map(int,input().split())
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))
 
INF=10**9

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

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

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
H, N = map(int, input().split())
L = []
for i in range(N):
    L.append(list(map(int, input().split())))
dp = [float("inf") for _ in range(H+1)] 
dp[0] = 0
for i in range(1, H+1):
    for j in range(N):
        a, b = L[j]
        if i <= a:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i-a] + b)
    # print(*dp)
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
H, N = map(int, input().split())
L = []
for i in range(N):
    L.append(list(map(int, input().split())))
dp = [float("inf") for _ in range(H+1)] 
dp[0] = 0
for i in range(1, H+1):
    for j in range(N):
        a, b = L[j]
        for k in range(i, min(H+1, i+a)):
            if k - a >= 0:
                dp[k] = min(dp[k], dp[i-1] + b)
            else:
                dp[k] = min(dp[k], b)
    # print(*dp)
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
print(min(dp[H:]))