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 -*-
h,n = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n)]
a = [i[0] for i in ab]
b = [i[1] for i in ab]

from math import ceil
dp = [[0] * (h + 1) for _ in range(n)]

for j in range(h+1):
    dp[0][j] = ceil(j/a[0]) * b[0]

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500000)
h, n = 0, 0
ab = None
dp = dict()

def input() -> str:
    return sys.stdin.readline().rstrip()

def f(i, j):
    if j <= 0:
        return 0
    if i < 0 and j > 0:
        return float("inf")
    ij = n * j + i
    if ij not in dp:
        dp[ij] = min([f(i - 1, j - k * ab[i][0]) + k * ab[i][1] for k in range((h - 1) // ab[i][0] + 2)])
    return dp[ij]

def main():
    global h, n, ab
    h, n = map(int, input().split())
    ab = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[0])
    print(f(n - 1, h))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
INF = float("inf")

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

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

dp = [[INF for i in range(h + 1)] for j in range(n + 1)]

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

for i in range(1, n + 1):  # 1<= i <= N
    for j in range(1, h + 1):  # 1 <= j <= W
        if j - items[i - 1][0] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - items[i - 1][0]] + items[i - 1][1],
                           dp[i][j - items[i - 1][0]] + items[i - 1][1])
        else:
            dp[i][j] = min(dp[i - 1][j], items[i - 1][1])

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

Submission status: Time Limit Exceeded

Solution code:
h,n = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for _ in range(n)]

inf = float('inf')
memo = [inf for _ in range(10**5)]
memo[0] = 0
for i in range(h+1):
    for x,y in l:
        memo[i+x] = min(memo[i+x],memo[i] + y)
print(min(memo[h:h+10000]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, N = (int(x) for x in input().split())

spells = []
for _ in range(N):
    a, b = (int(x) for x in input().split())

    spells.append((a,b))

spells.sort(key=lambda spell: spell[1] / spell[0])

best = {}
cheapest = float('inf')
q = deque()
q.append((0,0))
while len(q):
    h, c = q.popleft()

    if h >= H:
        cheapest = min(c, cheapest)
        continue

    if h in best and best[h] < c:
        continue

    best[h] = c

    for a,b in spells:
        h2 = h + a
        c2 = c + b

        if h2 not in best or best[h2] > c2:
            q.append((h2, c2))
            best[h2] = c2

print(cheapest)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, N = map(int, input().split())
N_list = []
for i in range(N):
    A, B = map(int, input().split())
    N_list.append([A, B])
N_list.sort(reverse = True)

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

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

print(dp[-1])

Submission status: Time Limit Exceeded

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


def solve():
    dp = [[float("infinity") for _ in range(H+1)] for _ in range(N+1)]
    for i in range(N):
        dp[i][0] = 0

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


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

Submission status: Time Limit Exceeded

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

dp=[100000000 for i in range(h+1)]
dp[0]=0
for i in range(h):
    for q in range(n):
        power=L[q][1]
        magic=L[q][2]
        dp[min(h,i+power)]=min(dp[min(h,i+power)],dp[i]+magic)

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from time import sleep
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from fractions import gcd
e = enumerate

sys.setrecursionlimit(10**7)
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [[float('inf')]*(H+1) for _ in range(N+1)]
#for i in range(H+1):
#    dp[0][i] = 0

#for i in range(N+1):
#    print(dp[i])


for i, ab in e(AB):
    a, b = ab[0], ab[1]
    for j in range(H+1):

        if j==0:
            newval = b
        elif j%a==0:
            newval = j//a * b
        else:
            newval = (j//a+1) * b

        if j>=a:
            newval2 = dp[i][j-a] + b
        else:
            newval2 = float('inf')

        if j>=a:
            newval3 = dp[i+1][j-a] + b
        else:
            newval3 = float('inf')

        dp[i+1][j] = min(dp[i][j], newval, newval2, newval3)

#    print(dp[i+1])
#    sleep(3)
#for i in range(N+1):
#    print(dp[i])

print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]

    AB.sort(key=lambda a: (a[0]/a[1], a[0]), reverse=True)

    S = []
    for a, b in AB:
        n = H // a + 1
        h = H
        i = 1
        while n >= i:
            S.append((a*i, b*i))
            n -= i
            i <<= 1
        if n:
            S.append((a*n, b*n))

    N2 = len(S)
    def ubound(b, a, i):
        for j in range(i, N2):
            aj, bj = S[j]
            if a + aj >= H:
                return (b+bj, b + (H-a) * bj / aj)
            a += aj
            b += bj

        return (inf, inf)

    q = []
    u0, u1 = ubound(0, 0, 0)

    inf = float("inf")
    heappush(q, (u1, u0, 0, 0, 0))
    um = u0
    #print(AB)
    #print(H, S)
    while q:
        #print(q)
        uq0, uq1, aq, bq, i = heappop(q)

        if uq0 > um:
            break

        if i >= N2: continue

        ai, bi = S[i]
        if aq + ai < H:
            heappush(q, (uq0, uq1, aq + ai, bq + bi, i + 1))

        u0, u1 = ubound(bq, aq, i + 1)
        if u1 <= um:
            if u0 < um:
                um = u0
            heappush(q, (u1, u0, aq, bq, i + 1))

    print(um)



if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
h,n,*t=map(int,open(0).read().split())
d=[0]+[9e9]*h
for a,b in zip(*[iter(t)]*2):
 for j in range(h+1):d[j]=min(d[j],d[max(0,j-a)]+b)
print(d[h])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
input=sys.stdin.readline
INF=1000000000
# A Dynamic Programming based Python Program for 0-1 Knapsack problem 
# Returns the maximum value that can be put in a knapsack of capacity W 
def knapSack(W,l, n):
    
    
    
    min_cost = [[0 for i in range(W+1)] for j in range(n+1)] 
    # fill 0th row with infinity 
    for i in range(W+1): 
        min_cost[0][i] = INF 
  
    # fill 0th column with 0 
    for i in range(1, n+1): 
        min_cost[i][0] = 0
    # now check for each weight one by one and fill the 
    # matrix according to the condition 
    for i in range(1, n+1): 
        for j in range(1, W+1): 
            # wt[i-1]>j means capacity of bag is 
            # less than weight of item 
            if (l[i-1][0] > j): 
                min_cost[i][j] = min(min_cost[i-1][j] ,l[i-1][1])
            # here we check we get minimum cost either 
            # by including it or excluding it 
            else: 
                min_cost[i][j] = min(min_cost[i-1][j], 
                    min_cost[i][j-l[i-1][0]] + l[i-1][1]) 
    
  
    # exactly weight W can not be made by given weights 
    if(min_cost[n][W] == INF): 
        return -1
    else: 
        return min_cost[n][W]

h,n=map(int,input().split())
l=list()
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b])
print( knapSack(h , l , n) )

Submission status: Time Limit Exceeded

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

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

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

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
n = input()    
m = n.split()
p = [int(i) for i in m] # p[0]体力p[1]魔法
list = []
for i in range(p[1]): #因数注意！
    n = input()    
    m = n.split()
    q = [int(i) for i in m] #1列の数列をリスト化
    list.append(q)

def knapsack(H,M,mahou):
    #期化
    inf=float("inf")
    dp=[[-inf for i in range(M+1)] for j in range(H+1)]
    for i in range(M+1):
        dp[0][i]=0
    for i in range(H+1):
        dp[i][0]=inf

    #DP
    for i in range(H):
        for w in range(M):
            if i+1 < mahou[w][0]: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
                dp[i+1][w+1] = min(dp[i+1][w],mahou[w][1]) 
            else:
                
                dp[i+1][w+1] = min(dp[i+1][w],dp[i+1-mahou[w][0]][w+1] + mahou[w][1])
    return dp[H][M]
print(knapsack(p[0],p[1],list))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

H,N=map(int,input().split())
L=[]
for i in range(N):
    T=[0,0,0]
    T[1],T[2]=map(int,input().split())
    T[0]=T[2]/T[1]
    L.append(T)
L=sorted(L)
n=1+H//L[0][1]
m=n*L[0][2]

def DP(MAX,minN,minM,i,T,M):
    t=T
    m=M
    if(T>=MAX):
        return M
    if(T<MAX):
        t+=L[i][1]
        m+=L[i][2]
        if(m<minM):        
            tm=DP(MAX,minN,minM,i,t,m)
            if(minM>tm):
                minM=tm
    if(len(L)-1 > i):
        t=T
        m=M
        if(m<minM):
            tm=DP(MAX,minN,minM,i+1,t,m)
            if(minN>tm):
                minM=tm
    return minM

tm=DP(H,10**10,m,0,0,0)

print(tm)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    h, n = map(int, args[0].split())

    AB = [tuple(map(int, s.split())) for s in args[1:]]

    inf = 10**12
    dp = [inf]*(h+1)
    dp[0] = 0
    for a, b in AB:
        for i, m in enumerate(dp):
            k = min(h, i+a)
            dp[k] = min(dp[k], dp[i]+b)

    return str(dp[-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
import sys

h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = [INF] * (h + 10001)
dp[0] = 0
for line in sys.stdin:
    a, b = map(int, line.split())
    for i in range(h):
        if dp[i] == INF:
            continue
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500000)

def input() -> str:
    return sys.stdin.readline().rstrip()

def f(i, j):
    if j <= 0:
        return 0
    if i < 0 and j > 0:
        return float("inf")
    ij = n * j + i
    if ij not in dp:
        dp[ij] = min([f(i - 1, j - k * ab[i][0]) + k * ab[i][1] for k in range((h - 1) // ab[i][0] + 2)])
    return dp[ij]

h, n = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[0])
dp = dict()
print(f(n - 1, h))

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
Cost=[]
for i in range(N):
  A, B = map(int, input().split())
  Cost.append((A, B))
#  Cost.append((A, B, A/B))
#Cost = sorted(Cost, key=lambda row: row[0], reverse=True)
#sortedCost = sorted(Cost, key=lambda row: row[2], reverse=True)

DP=[float('inf')]*(H+2)
DP[0]=0
DP[1]=0
for i in range(2,H+2):
    for j in range(N):
      if i-Cost[j][0]>=0:
          DP[i]=min(DP[i], DP[i-Cost[j][0]]+Cost[j][1])
      else:
          DP[i]=min(DP[i], Cost[j][1])

print(DP[H+1])

Submission status: Time Limit Exceeded

Solution code:

H, N = (int(x) for x in input().split())

spells = []
for _ in range(N):
    a, b = (int(x) for x in input().split())

    spells.append((a,b))

spells.sort(reverse=True)

best = {}
best[0] = 0
cheapest = float('inf')
stack = [(0, 0)]
while len(stack):
    h, c = stack.pop()

    if h >= H:
        cheapest = min(c, cheapest)
        continue

    for a,b in spells:
        h2 = h + a
        c2 = c + b

        if h2 not in best or best[h2] > c2:
            stack.append((h2, c2))

            best[h2] = c2

print(cheapest)

Submission status: Time Limit Exceeded

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

l = sorted([[int(i) for i in input().split()] for _ in range(n)],key = lambda x: x[0])

inf = float('inf')
memo = [inf for _ in range(10**5)]
memo[0] = 0
for i in range(h+1):
    for x,y in l:
        memo[i+x] = min(memo[i+x],memo[i] + y)
print(min(memo[h:]))

Submission status: Time Limit Exceeded

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

dp = [float('inf') for i in range(2*10**4)]
dp[0] = 0

for i in range(2*10**4):
    m = []
    for j in range(N):
        if i-A[j] >= 0:
            m.append(dp[i-A[j]]+B[j])
    m.append(dp[i])
    dp[i] = min(m)

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
G = [0 for i in range(N)]
for i in range(N):
    A, B = map(int, input().split())
    koritu = A / B
    G[i] = (koritu, A, B)
G.sort(reverse = True)
#print(G)
dp = [[0 for i in range(H+1)] for j in range(N)]
k, a, b = G[0]
for i in range(1, H + 1):
    dp[0][i] = ((i - 1) // a + 1) * b
for j in range(1, N):
    k, a, b = G[j]
    for i in range(1, H+1):
        if i >= a:
            dp[j][i] = min(dp[j-1][i], dp[j][i-a] + b)
        else:
            dp[j][i] = min(dp[j-1][i],b)
print(dp[N-1][H])

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, floor

h, n = map(int, input().split())
l = []
for _ in range(n):
  l.append(list(map(int, input().split())))

if n == 1:
  print(ceil(h/l[0][0]) * l[0][1])
  exit(0)

dp = [ceil(hp/l[0][0]) * l[0][1] for hp in range(h + 1)]


for i in range(1, n):
  for hp in range(h + 1):
    if hp >= l[i][0]:
      dp[hp] = min([dp[hp], dp[hp - l[i][0]] + l[i][1]])
    else:
      dp[hp] = min([dp[hp], l[i][1]])

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for ii in range(N)]
C = [0]*(H+1)
for ii in range(1,H+1):
    for jj in AB:
        if ii>=jj[0]:
            if C[ii]==0:
                C[ii] = C[ii-jj[0]]+jj[1]
            else:
                C[ii] = min(C[ii], C[ii-jj[0]]+jj[1])
        else:
            if C[ii]==0:
                C[ii] = jj[1]
            else:
                C[ii] = min(C[ii], jj[1])
print(C[H])

Submission status: Time Limit Exceeded

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

maxa = max(a)
mina = min(a)
maxn = h//mina + 1
dp = [float("inf") for _ in range(maxa + h)]
dp[0] = 0

for i in range(maxn):
    for j in range(maxa + h):
        for k in range(n):
            if a[k] <= j:
                dp[j] = min(dp[j-a[k]]+b[k], dp[j])

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
magics = []
for i in range(n):
    a, b = map(int, input().split())
    magics.append((a, b))
h_table = [float("inf") for _ in range(h + 1)]
h_table[0] = 0
for i in range( h + 1):
    for a, b in magics:
        h_table[min(i + a, h)] = min(h_table[min(i + a, h)], h_table[i] + b)
print(h_table[h])

Submission status: Time Limit Exceeded

Solution code:
from itertools import count
 
H, N = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(N)]
 
dp = [10 ** 9 for _ in range(H + 1)]
dp[0] = 0
for hp in range(1, H + 1):
    for A, B in ABs:
        if A <= hp:
            dp[hp] = min(dp[hp], dp[hp - A] + B)
        else:
            dp[hp] = min(dp[hp], B)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def calc_m_value(M, A, B, N, h):
    m_cand = []
    for i in range(N):
        index = h - A[i]
        if (index < 0):
            m = B[i]
        else:
            m = M[index] + B[i]
        m_cand.append(m)
    return min(m_cand)

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)

M = [0]
for i in range(1, H+1):
    M.append(calc_m_value(M, A, B, N, i))

print(M[H])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
magics = []
for _ in range(n):
    a, b = map(int, input().split())
    magics.append((a,b))

mins = [None]*(h+1)
mins[0] = 0
ind = 0
while ind < h:
    for a, b in magics:
        target = min(h, ind+a)
        if mins[target] is None:
            mins[target] = b + mins[ind]
        else:
            mins[target] = min(b + mins[ind], mins[target])
    ind += 1
    while True:
        if mins[ind] is not None:
            break
        ind += 1
print(mins[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)]

INF = 10**10
#print(magic)

AM = 0
for i in range(N):
    AM = max(AM,magic[i][0])
#print(AM)


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

for i in range(1,H+AM+1):
    for j in range(N):
        if magic[j][0] > i:
            dp[i] = min(dp[i],magic[j][1])
        else:
            dp[i] = min(dp[i-magic[j][0]]+magic[j][1],dp[i])
ans = INF
for i in range(H,H+AM+1):
    ans = min(ans,dp[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = []
b = []
m = []
for i in range(n):
    at, bt = map(int, input().split()) # a_tmp, b_tmp
    a.append(at)
    b.append(bt)

dp = np.zeros((n+1,h+1))
dp = [[0] * (h+1) for i in range(n+1)]
# print(dp2)

for i in range(n):
    for j in range(h):
        # print("Test")
        if j - a[i] < 0:
            o = b[i]
        else:
            o = dp[i+1][j+1-a[i]] + b[i]
        if i != 0:
            dp[i+1][j+1] = min(dp[i][j+1], o)
        else:
            dp[i+1][j+1] = o

print(int(dp[n][h]))

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
M=[list(map(int,input().split())) for _ in range(n)]
dp = [[-(-i//M[0][0])*M[0][1] for i in range(1,h+1)] for _ in range(n)]
for i in range(1,n):
  for j in range(h):
    if j<M[i][0]:
      dp[i][j]=min(dp[i-1][j],M[i][1])
    else:
      dp[i][j]=min(dp[i-1][j],dp[i][j-M[i][0]]+M[i][1])
print(dp[n-1][h-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
def main():
    dp = defaultdict(lambda: 10**10)
    
    # print(sys.stdin.readline.split())
    h,n = [int(j) for j in sys.stdin.readline().split()]
    l = [] 

    for i in range(n):
        a,b = [int(j) for j in sys.stdin.readline().split()]
        l.append((b,a))
    l.sort()
    # print(l)
    for i in range(n):
        for j in range(1,l[0][1]+1):
            dp[i, j] = l[0][0]
    for i in range(n):
        for j in range(1, h+1):
            # print(i,j, dp[i-1, j])
            dp[i,j] = dp[i-1, j]
            if j>l[i][1]:
                dp[i,j] = min(dp[i-1, j], dp[i, j-l[i][1]]+l[i][0])
            else:
                dp[i,j] = min(dp[i-1, j], l[i][0])
    sys.stdout.write(str(dp[n-1, h]))
    sys.stdout.write('\n')
if __name__ == "__main__": 
    main()     
# print(dp[n-1, h])

Submission status: Time Limit Exceeded

Solution code:
H , N = map( int,  input().strip().split(" ") ) ;
L = [] ;
for x in range ( N ) :
	L.append ( list( map ( int  ,input().strip().split(" ") ) ) ) ;

arr = [ 0 for x in range ( H +1 ) ] ;

for x in range ( 1 , H + 1 ) :

	v0 = -1 ;	
	for t in L :
		if x - t[0] <= 0 :
			v = t[1] ;
		else :
			v = t[1] + arr[ x -t[0]  ] ;

		if v0 == -1 :
			v0 = v ;
		else :
			v0 = min ( v0 , v ) ; 
	arr[x] = v0 ;
print ( arr[H]) ;

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int,input().split())
magic=[]
for i in range(n):
    a,b=map(int,input().split())
    magic.append([a,b])
dp = [1000000000000 for i in range(h+1)]
dp[0] = 0
for i in range(h):
    for a,b in magic:
        rest = min(i+a,h)
        dp[rest] = min(dp[rest],dp[i]+b)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, N = map(int, input().split())
a = []
b = []
a.append(10**9)
b.append(10**9)

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

dp = np.zeros((N+1,H+1))

a = np.array(a)
b = np.array(b)

#b *= -1

for i in range(N+1):
    dp[i][0] = b[i]
for j in range(H+1):
    dp[0][j] = 10**9

#print(dp)

for i in range(1,N+1):
    for h in range(1,H+1):
        #print(i,h)
        if h > a[i]:
            dp[i][h] = min(dp[i][h-a[i]]+b[i],dp[i-1][h])
        else:
            dp[i][h] = dp[i][h-1]
        #print(dp)
#print('ans')
#print(dp)
print(int(dp[N][H]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

h, n = na()
a, b = [], []
for _ in range(n):
    ai, bi = na()
    a.append(ai)
    b.append(bi)
inf = 10**9
dp = [[inf]* (10**4+1) for _ in range(n+1)]
for i in range(n):
    for j in range(1, 10**4+1):
        if j < a[i]:
            dp[i+1][j] = min(dp[i][j],((j-1)//a[i]+1)*b[i])
        else:
            dp[i+1][j] = min(dp[i][j],((j-1)//a[i]+1)*b[i], 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())
G = [0 for i in range(N)]
for i in range(N):
    A, B = map(int, input().split())
    koritu = A / B
    G[i] = (koritu, A, B)
G.sort(reverse = True)
#print(G)
dp = [[0 for i in range(H+1)] for j in range(N)]
for j in range(N):
    k, a, b = G[j]
    if j == 0:
        for i in range(1,H+1):
            dp[j][i] = ((i-1)//a+1) * b
    else:
        for i in range(1, H+1):
            if i >= a:
                dp[j][i] = min(dp[j-1][i], dp[j][i-a] + b)
            else:
                dp[j][i] = min(dp[j-1][i],b)
print(dp[N-1][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)

xx=-1
for i in range(N):
    x=A[i]/B[i]
    if x>xx:
        xx=x
        y=i

n=N
w=B #重さ
v=A #値段
W=H #最大容量
W=(H//A[y]+1)*B[y]

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

for k in range(W+1):
    if dp[n][k]>=H:
        ans=k
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))
ma=[]
for _ in range(n):
    tmp=list(map(int,input().split()))
    ma.append(tmp)
ma=sorted(ma,key=lambda x:x[1])
ma.reverse()
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
for i in range(n):
    dp[i][0]=0
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0][0])*ma[0][1]
#print(np.array(ma))
for i in range(1,n):
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(1,h+1):
        if j<ma[i][0]:
            cal=ma[i][1]
        else:
            #print("sansyo before")
            cal=ma[i][1]+dp[i][j-ma[i][0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

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

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

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

print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
import collections

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

INF = 10 ** 20

dp = collections.defaultdict(lambda : INF)
dp[0] = 0

magic = []

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



que = [0]
cc = [0]
m = 0
c = 0
while que:
    next_que = set()
    for now_dam in que:
        for a, b in magic:
            dam = now_dam + a
            if dp[dam] > dp[now_dam] + b:
                dp[dam] = dp[now_dam] + b
                if h > dam:
                    next_que.add(dam)
    que = list(next_que)
ans = INF

for k, v in dp.items():
    if k >= h:
        ans = min([v, ans])

print(ans)

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)

inf = 10**23

d = [inf] * (H+1)
d[0] = 0
for i in range(1, H+1):
    for abi in range(N):
        if A[abi] >= i:
            d[i] = min(d[i], B[abi])
        else:
            d[i] = min(d[i], d[i-A[abi]] + B[abi])


print(d[H])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = []
b = []
m = []
for i in range(n):
    at, bt = map(int, input().split()) # a_tmp, b_tmp
    a.append(at)
    b.append(bt)

dp = np.zeros((n+1,h+1))

for i in range(n):
    for j in range(h):
        # print("Test")
        if j - a[i] < 0:
            o = b[i]
        else:
            o = dp[i+1][j+1-a[i]] + b[i]
        if i != 0:
            dp[i+1][j+1] = min(dp[i][j+1], o)
        else:
            dp[i+1][j+1] = o

print(int(dp[n][h]))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500000)

def input() -> str:
    return sys.stdin.readline().rstrip()

def f(i, j):
    if j <= 0:
        return 0
    if i < 0 and j > 0:
        return float("inf")
    if (i, j) not in dp:
        dp[(i, j)] = min([f(i - 1, j - k * ab[i][0]) + k * ab[i][1] for k in range((h - 1) // ab[i][0] + 2)])
    return dp[(i, j)]

h, n = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[0])
dp = dict()
print(f(n - 1, h))

Submission status: Time Limit Exceeded

Solution code:
#E変更
#入力
H,N=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]#[攻撃,魔力]
#処理
As=sorted(M,key=lambda x:x[0])
Bs=sorted(M,key=lambda x:x[1])

def E(h):#体力hの相手に対して最も最小の魔力消費
    X=[]#0から最小の消費魔力を代入 
    for i in range(h+1):
        if i==0:
            X.append(0)
        else:
            def y(j):
                if i-M[j][0]<0:
                    return 0
                else:
                    return i-M[j][0]
            Z= min( [ X[y(j)] +M[j][1] for j in range(N)] )
            X.append(Z)
    return X[h]
print(E(H))

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
a=[]
ab=[]

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

loop=h+max(a)
cost=[-1 for i in range(loop)]
cost[0]=0
i=0
costlist=[]
while i<loop:
    costlist.clear()
    for j in range(n):
        ii=i-ab[j][0]
        if (0<=ii<h)&(cost[ii]>=0):
            costlist.append(cost[ii]+ab[j][1])
    if len(costlist)!=0:
        cost[i]=min(costlist)
    i+=1
acost=[i for i in cost[h:] if i!=-1]
ans=min(acost)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
H, N = map(int, input().split())

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

AB = sorted(
  (list(map(int, input().split())) for i in range(N)),
  key=lambda x: x[0] / x[1],
  reverse=True
)

def recursive(health, magic_point):
  health = min(H, health)
  if dp[health] <= magic_point:
    return
  dp[health] = min(dp[health], magic_point)
  if health == H:
    return
  for a, b in AB:
    recursive(health + a, magic_point + b)

recursive(0, 0)
print(dp[-1])