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:
# coding: utf-8
# Your code here!
def main():
    import math
    h,n = map(int, input().split())
    aa = [0]*(n+1)
    bb = [0]*(n+1)
    mp = [[None for _ in range(n+1)] for _ in range(h+1)]
    # 体力i 技の種類j
    for j in range(1, n+1):
      mp[0][j] = 0
      aa[j], bb[j] = map(int, input().split())
    for i in range(1, h+1):
        mp[i][0] = float("inf")
    for j in range(1, n+1):
        for i in range(1, h+1):
        	mp[i][j] = min(mp[i][j-1], mp[max(0, i - aa[j])][j] + bb[j])
    print(mp[h][n])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heapify, heappop, heappush
CostMax = 10**9
inpl = lambda: list(map(int,input().split()))
H, N = inpl()
AB = [inpl() for _ in range(N)]
AB.sort(key=lambda x: (x[1], -x[0]))
A = []
B = []
for a, b in AB:
    if len(A)==0 or a > A[-1]:
        A.append(a)
        B.append(b)
L = len(A)
prevcost = defaultdict(lambda: CostMax)

q = [(0,0,0)] # position, last, cost
ans = CostMax
while q:
    pos, last, cost = heappop(q)
    if cost >= prevcost[pos]:
        continue
    else:
        prevcost[pos] = cost
        for n in range(last,L):
            new_pos = pos + A[n]
            new_cost = cost + B[n]
            if new_cost > ans:
                continue
            elif new_pos >= H:
                ans = min(ans, new_cost)
            else:
                heappush(q, (new_pos, n, new_cost))
print(ans)

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):
    for j in range(N):
        if i < A[j]:
            dp[i] = min(dp[i], B[j])
        else:
            dp[i] = min(dp[i], dp[i-A[j]] + B[j])
            
print(int(dp[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())
    
maxA = np.max(A)
    
dp = np.full(H+1, np.inf)
dp[0] = 0
for i in range(1,H+1):
    for j in range(N):
        if i < A[j]:
            dp[i] = min(dp[i], B[j])
        else:
            dp[i] = min(dp[i], dp[i-A[j]] + B[j])
            
print(int(dp[H]))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def main():
    import math
    h,n = map(int, input().split())
    aa = [None for _ in range(n+1)]
    bb = [None for _ in range(n+1)]
    mp = [[None for _ in range(n+1)] for _ in range(h+1)]
    # 体力i 技の種類j
    for j in range(1, n+1):
      mp[0][j] = 0
      aa[j], bb[j] = map(int, input().split())
    for i in range(1, h+1):
        mp[i][0] = float("inf")
    for j in range(1, n+1):
        for i in range(1, h+1):
        	mp[i][j] = min(mp[i][j-1], mp[max(0, i - aa[j])][j] + bb[j])
    print(mp[h][n])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def main():
    import math
    h,n = map(int, input().split())
    aa = [None for _ in range(n+1)]
    bb = [None for _ in range(n+1)]
    mp = [[None for _ in range(n+1)] for _ in range(h+1)]
    # 体力i 技の種類j
    for j in range(1, n+1):
      aa[j], bb[j] = map(int, input().split())
    for i in range(1, h+1):
        mp[i][0] = float("inf")
    for j in range(1, n+1):
        for i in range(1, h+1):
            if i - aa[j] >= 1:
              # print(i, j, i - aa[j])
              mp[i][j] = min(mp[i][j-1], mp[i - aa[j]][j] + bb[j])
            else:
              mp[i][j] = min(mp[i][j-1], bb[j])
    print(mp[h][n])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import math
h,n = map(int, input().split())
aa = [None for _ in range(n+1)]
bb = [None for _ in range(n+1)]
mp = [[None for _ in range(n+1)] for _ in range(h+1)]
# 体力i 技の種類j
for j in range(1, n+1):
  aa[j], bb[j] = map(int, input().split())
for i in range(1, h+1):
    mp[i][0] = float("inf")
for j in range(1, n+1):
    for i in range(1, h+1):
        if i - aa[j] >= 1:
          # print(i, j, i - aa[j])
          mp[i][j] = min(mp[i][j-1], mp[i - aa[j]][j] + bb[j])
        else:
          mp[i][j] = min(mp[i][j-1], bb[j])
print(mp[h][n])

Submission status: Time Limit Exceeded

Solution code:
h,n = list(map(int, input().split()))
ab = []
a = []
b = []
for _ in range(n):
    t_ab = list(map(int, input().split()))
    ab.append(t_ab)
    a.append(t_ab[0])
    b.append(t_ab[1])

maxa = max(a)
hmaxa = h+maxa
dp = [float("inf") for _ in range(hmaxa)]
dp[0] = 0

for i in range(hmaxa):
    ab_child = [dp[i]]
    for j in ab:
        if j[0] <= i:
            ab_child.append(dp[i-j[0]] + j[1])
        dp[i] = min(min(ab_child), dp[i])

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
h,n = list(map(int, input().split()))
ab = []
a = []
b = []
for _ in range(n):
    t_ab = list(map(int, input().split()))
    ab.append(t_ab)
    a.append(t_ab[0])
    b.append(t_ab[1])

maxa = max(a)
hmaxa = h+maxa
dp = [float("inf") for _ in range(hmaxa)]
dp[0] = 0

for i,name in enumerate(a):
    a_n = (h+name-1)//name
    for _ in range(a_n):
        for j in range(hmaxa-1):
            if name+j <= hmaxa-1:
                dp[j+name] = min(dp[j]+b[i], dp[j+name])

print(min(dp[h:]))

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(H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            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:
import sys

input = sys.stdin.readline
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

dp = [0] * (H + 1)

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

ans = dp[H]

print(ans)

Submission status: Time Limit Exceeded

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

dp = [0] * (H + 1)

for i in range(1, H + 1):
    min_cost = 10 ** 8
    for j in range(N):
        damage, cost = magic[j]
        min_cost = min(dp[max(i - damage, 0)] + cost, min_cost)
    dp[i] = min_cost

ans = dp[H]

print(ans)

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(H):
        if dp[i] == INF:
            continue
        else:
            for j in range(N):
                if dp[i]+AB[j][1] < dp[i+AB[j][0]]:
                    dp[i+AB[j][0]] = dp[i]+AB[j][1]
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

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+1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            tmp1 = dp[i]
            for j in range(N):
                tmp2 = AB[j][1]
                tmp3 = AB[j][0]
                if tmp1+tmp2 < dp[i+tmp3]:
                    dp[i+tmp3] = tmp1+tmp2
    print(min(dp[H:]))

if __name__ == '__main__':
    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[i] = : min used MP when mosterHP==i

DP[-1] = 0
for i in reversed(range(H+1)):
    for a, b in L:
        if i-a >= 0:
            DP[i-a] = min(DP[i] + b, DP[i-a])
        else:
            DP[0] = min(DP[0], DP[i]+b)
print(DP[0])

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)

# N -> dp[N - A_i] + B_i

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

for i in range(H+1):
  temp = 10 ** 8 + 1
  for j in range(N): # Use each Magic j
    if i - A[j] > 0:
      temp = min(temp, dp[ i - A[j] ] + B[j] )
    else:
      temp = min(temp, B[j] )
  dp[i] = temp
               
print(dp[H])

Submission status: Time Limit Exceeded

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    INF = float('inf')
    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:
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+1)
    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:
def main():
    INF = float('inf')
    H,N = map(int,input().split())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    dp = [INF]*(H+max(A)+1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            tmp1 = dp[i]
            for j in range(N):
                tmp2 = tmp1 + B[j]
                if tmp2 < dp[i+A[j]]:
                    dp[i+A[j]] = tmp2
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    INF = float('inf')
    H,N = map(int,input().split())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    dp = [INF]*(H+max(A)+1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            for j in range(N):
                if dp[i]+B[j] < dp[i+A[j]]:
                    dp[i+A[j]] = dp[i]+B[j]
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    INF = 10**9
    H,N = map(int,input().split())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    dp = [INF]*(H+max(A)+1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            for j in range(N):
                if dp[i]+B[j] < dp[i+A[j]]:
                    dp[i+A[j]] = dp[i]+B[j]
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    INF = 10**9
    H,N = map(int,input().split())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    dp = [INF]*(H+max(A))
    dp[0] = 0
    for i in range(N):
        for j in range(A[i],H+max(A)):
            dp[j] = min(dp[j],dp[j-A[i]]+B[i])
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
dp = [ 0 for _ in range(H+1)]
dp[0] = 0
AB = [list(map(int, input().split())) for _ in range(N)]
for j in range(1, H+1):
  dp[j] = min([dp[max(0, j-a)] + b for a, b in AB])
print(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**9+1] * (h+1)
dp[0] = 0

for i in range(h):
  for a, b in ab:
    k = min(i+a, h)
    dp[k] = min(dp[k], dp[i]+b)

print(dp[h])

Submission status: Time Limit Exceeded

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

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

for i in range(h):
    for j in range(n):
        if (i+a[j])>2*10000:
            dp[2*10000]=min(dp[2*10000],dp[i]+b[j])
            continue
        dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j])

ans=float("inf")
for j in range(h,2*10000+1):
    ans=min(ans,dp[j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, N = map(int, input().split())
#dp = [ float("inf") for _ in range(H+1)]
dp = np.array([float("inf")]*(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)
    dp[nj] = min(dp[nj], dp[j] + B)

    
print(int(dp[H]))

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
dp = [ float("inf") for _ in range(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)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
h,n,*a=map(int,open(0).read().split());l=20000;t=[0]*l
for i in range(1,l):t[i]=min(t[i-p]+q for p,q in zip(a[::2],a[1::2]))
print(min(t[h:]))

Submission status: Time Limit Exceeded

Solution code:
h,n,*a=map(int,open(0).read().split());l=10**5+h;t=[0]*l
for i in range(1,l):t[i]=min(t[i-p]+q for p,q in zip(a[::2],a[1::2]))
print(min(t[h:]))

Submission status: Time Limit Exceeded

Solution code:
h,n,*a=map(int,open(0).read().split());l=10**5+h;t=[0]*l
for i in range(1,l):t[i]=min(t[i-p]+q for p,q in zip(a[::2],a[1::2]))
print(min(t[h::2]))

Submission status: Time Limit Exceeded

Solution code:
H,N = map(int,input().split())
magic = []
for i in range(N):
  a,b = map(int,input().split())
  magic.append((a,b))
A = [item[0] for item in magic]
maxA = max(A)
minA = min(A)
dp = [float("inf")]*(H+maxA+1)
dp[0]=0

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

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 

 
#main
h,n=map(int,input().split())
AB=[list(map(int,input().split())) for a in range(n)]
dp=[[inf for b in range(h+1+10000)] for a in range(n+1)]
dp[0][0]=0

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

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(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)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])

Submission status: Time Limit Exceeded

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

#output
M = max(A)
inf = 10**10
dp = [inf]*(H+(M+1))
dp[0] = 0
for i in range(N):
    for j in range(A[i], H+M):
        dp[j] = min(dp[j], dp[j-A[i]] + B[i])

answer = min(dp[H:(H+M+1)])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
INT_MAX = 10**8
h, n = map(int, input().split())
e = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [0] + [INT_MAX]* h
for i in range(1, h+1):
  v = INT_MAX
  for a, b in e:
    c = dp[max(0, i - a)] + b
    v = min(v, c)
  dp[i] = v
print(dp[h])

Submission status: Time Limit Exceeded

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

#output
M = max(A)
inf = 10**10
dp = [inf]*(H+(M+1))
dp[0] = 0
for i in range(N):
    for j in range(A[i], H+M):
        dp[j] = min(dp[j], dp[j-A[i]] + B[i])

answer = min(dp[H:(H+M+1)])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
INT_MAX = 10**8
h, n = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(n)]

dp = [INT_MAX] * (h+1)
dp[0] = 0
for i in range(1, h+1):
  for a, b in e:
    c = dp[max(0, i - a)] + b
    dp[i] = min(dp[i], c)

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
INT_MAX = 10**8
h, n = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(n)]

dp = [0] + [INT_MAX]* h
for i in range(1, h+1):
  for a, b in e:
    c = dp[max(0, i - a)] + b
    dp[i] = min(dp[i], c)

print(dp[h])

Submission status: Time Limit Exceeded

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

dplength = H+max(A)+1
INF = 100000000000
# dp[i] : 体力をi減らすための魔力の最小値
dp = [ INF for _ in range(dplength)]
dp[0] = 0
answer = INF
for i in range(dplength):
  for j in range(N):
    if A[j] <= i:
      dp[i] = min(dp[i], dp[i-A[j]] + B[j])
    else:
      dp[i] = min(dp[i], B[j])
  if H <= i:
    answer = min(answer, dp[i])

print(answer)

Submission status: Time Limit Exceeded

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

A = [ab[0] for ab in AB]
B = [ab[1] for ab in AB]

INF = 100000000000
# dp[i] : 体力をi減らすための魔力の最小値
dp = [ INF for _ in range(H+max(A)+1)]
dp[0] = 0

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

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

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
 
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_max = 10000000000
dp = [dp_max for i in range(H+1)]
#dp = np.full(H+1, dp_max, dtype=int)
dp[0] = 0
 
for i in range(H+1):
  if dp[i] == dp_max:
    continue
 
  for j in range(N):
    ni = min(H, i + A[j])
 
    dp[ni] = min(dp[ni], dp[i] + B[j])
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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_max = 10000000000
dp = np.full(H+1, dp_max, dtype=int)
dp[0] = 0

for i in range(H+1):
  if dp[i] == dp_max:
    continue

  for j in range(N):
    ni = min(H, i + A[j])

    dp[ni] = min(dp[ni], dp[i] + B[j])
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
import math
h,n=map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(n)] ,key=lambda x:x[0])
amax=X[-1][0]
l=[10**9 for i in range(h+amax)]
l[0]=0
for i in range(h):
    for j in range(n):
        temp=X[j][1]
        if l[i]+temp<l[i+X[j][0]]:
            l[i+X[j][0]]=l[i]+temp
lnew=l[h:]
ans=min(lnew)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int,input().split())
dg = 10**5

ba = []
for _ in [0]*n:
    a,b = map(int,input().split())
    if a >= h:
        a = h
    ba.append(b*dg + a)
ba.sort()

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

for i in range(1, h+1):
    for e in ba:
        a,b = e%dg, e//dg
        if i<=a:
            if d[i] > b:
                d[i] = b
        else:
            if d[i] > d[i-a]+b:
                d[i] = d[i-a]+b
print(d[-1])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

H, N = map(int, input().split())
M = [tuple(map(int, input().split())) for _ in range(N)]
M.sort()
A = [0] * N
B = [0] * N
for i, (a, b) in enumerate(M):
    A[i] = a
    B[i] = b


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

for i in range(H):
    for j in range(N):
        ni = min(H, i + A[j])
        b = B[j]
        dp[ni] = min(dp[ni], dp[i] + b)

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=np.array([[inf for i in range(W+1)] for j in range(N+1)])
  dp[0][0]= 0
  #DP
  for i in range(N):
    for w in range(W+1):
      if 0 <= w-weight[i]: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w])
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
H,N = map(int,input().split())
 
weight=[]
value=[]
for i in range(N):
    n,a=input().split()
    weight.append(int(n))
    value.append(int(a))
MAX = max(weight)
dp = knapsack(N,H+MAX,weight,value)
 
print(int(min(dp[N][H:H+MAX])))

Submission status: Time Limit Exceeded

Solution code:
def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[inf for i in range(W+1)] for j in range(N+1)]
  dp[0][0]= 0
  #DP
  for i in range(N):
    for w in range(W+1):
      if 0 <= w-weight[i]: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w])
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
H,N = map(int,input().split())
 
weight=[]
value=[]
for i in range(N):
    n,a=input().split()
    weight.append(int(n))
    value.append(int(a))
MAX = max(weight)
dp = knapsack(N,H+MAX,weight,value)
 
print(min(dp[N][H:H+MAX]))

Submission status: Time Limit Exceeded

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

inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(N):
    A, B = map(int, input().split())
    for j in range(H):
        t1 = j + A
        if t1 > H:
            t1 = H
        t2 = dp[j] + B
        if t2 < dp[t1]:
            dp[t1] = t2
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    max_A = max(a for a, _ in AB)
    inf = float('inf')
    dp = [inf] * (H + max_A + 1)
    dp[0] = 0
    for i in range(1, H + max_A + 1):
        for a, b in AB:
            t1 = i - a
            if t1 < 0:
                continue
            t2 = dp[t1]
            if t2 == inf:
                continue
            if t2 + b < dp[i]:
                dp[i] = t2 + b
    print(min(dp[H:]))
main()

Submission status: Time Limit Exceeded

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

max_A = max(a for a, _ in AB)
inf = float('inf')
dp = [inf] * (H + max_A + 1)
dp[0] = 0
for i in range(1, H + max_A + 1):
    for a, b in AB:
        t1 = i - a
        if t1 < 0:
            continue
        t2 = dp[t1]
        if t2 == inf:
            continue
        if t2 + b < dp[i]:
            dp[i] = t2 + b
print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

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

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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()

H,N = LI()
A = []
B = []
for i in range(N):
    a,b = LI()
    A.append(a)
    B.append(b)

dp = [inf]*(H+1)
ans = inf

dp[H] = 0

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

Submission status: Time Limit Exceeded

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

for a, b in ab:
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,N=map(int,input().split())
ABlist=[[0]*2 for _ in range(N)]
for i in range(N):
    ABlist[i][0],ABlist[i][1]=map(int,input().split())
AB=np.array(ABlist)
A=AB[:,0]
B=AB[:,1]
Z=[0]+[10**8]*H
z=[0]*(H+1)
for i in range(1,H+1):
    for a,b in zip(A,B):
        k=i-a
        if k<=0:
            z[i]=b
        else:
            z[i]=Z[k]+b
        if z[i]<Z[i]:Z[i]=z[i]


print(Z[H])

Submission status: Time Limit Exceeded

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

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

for i in range(1, H + 1):
    values = []
    for a, b in ab:
        values.append(dp[i - a] + b)
    dp[i] = min(values)

print(dp[H])

Submission status: Time Limit Exceeded

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

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

for i in range(1, H + 10 ** 4 + 1):
    values = []
    for a, b in ab:
        values.append(dp[i - a] + b)
    dp[i] = min(values)

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
H,N = map(int,input().split())
spells = sorted([tuple(map(int,input().split())) for _ in range(N)])
max_a = spells[-1][0]

dp = [10000000000 for _ in range(H + max_a + 1)]
dp[0] = 0

for i in range(1, H + max_a + 1):
  for spell in spells:
    if spell[0] > i:
      break
    else:
      dp[i] = min(dp[i], dp[i - spell[0]] + spell[1])

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

    dp = np.zeros(h+1, dtype='i8')
    for i in range(h):
        dp[i] = 10**18
    for i in range(h, 0, -1):
        for j in range(n):
            dp[max(0, i-ab[j][0])] = min(dp[max(0, i - ab[j][0])], dp[i] + ab[j][1])

    print(dp[0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
for _ in range(n):
    a, b = map(int, input().split())
    for start in range(h):
        if dp[start]==10**10:
            continue
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:

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

    dp = []
    for i in range(h+1):
        dp.append(10**18)
    dp[h] = 0
    for i in range(h, 0, -1):
        for j in range(n):
            dp[max(0, i-ab[j][0])] = min(dp[max(0, i - ab[j][0])], dp[i] + ab[j][1])

    print(dp[0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

max_v = 10100
x = float("inf")

dp = [x] * max_v

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

ans = x
for i in range(max_v):
    if i >= h:
        ans = min(ans, dp[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, n = map(int, input().split())
dp = np.array([10**10]*(h+1))
dp[0] = 0
for _ in range(n):
    a, b = map(int, input().split())
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])

Submission status: Time Limit Exceeded

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

dp=[0]+[None]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=[0]+[None]*H
    for j in range(A,H+1):
        if dp[j]==None:
            if ndp[j-A]!=None:
                ndp[j]=ndp[j-A]+B
            continue
        
        if ndp[j-A]==None:
            if dp[j]!=None:
                ndp[j]=dp[j]
            
            continue

        ndp[j]=min(ndp[j-A]+B,dp[j])

    for j in range(max(H-A+1,0),H+1):
        if ndp[j]==None:
            continue

        if ndp[-1]!=None:
            ndp[-1]=min(ndp[j]+B,ndp[-1])
        else:
            ndp[-1]=ndp[j]+B
    
    if A >= H and dp[-1]!=None:
        ndp[-1]=min(B,dp[-1])

    dp=ndp

print(dp[-1])