Problem:


Score : 500 points

Problem Statement

Ibis is fighting with a monster.

The health of the monster is H.

Ibis can cast N kinds of spells. Casting the i-th spell decreases the monster's health by A_i, at the cost of B_i Magic Points.

The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.

Ibis wins when the health of the monster becomes 0 or below.

Find the minimum total Magic Points that have to be consumed before winning.

Constraints

1 \leq H \leq 10^4

1 \leq N \leq 10^3

1 \leq A_i \leq 10^4

1 \leq B_i \leq 10^4

All values in input are integers.

Input

Input is given from Standard Input in the following format:

H N
A_1 B_1
:
A_N B_N

Output

Print the minimum total Magic Points that have to be consumed before winning.

Sample Input 1

9 3
8 3
4 2
2 1

Sample Output 1

4

First, let us cast the first spell to decrease the monster's health by 8, at the cost of 3 Magic Points. The monster's health is now 1.

Then, cast the third spell to decrease the monster's health by 2, at the cost of 1 Magic Point. The monster's health is now -1.

In this way, we can win at the total cost of 4 Magic Points.

Sample Input 2

100 6
1 1
2 3
3 9
4 27
5 81
6 243

Sample Output 2

100

It is optimal to cast the first spell 100 times.

Sample Input 3

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

Sample Output 3

139815



Sample input:
9 3
8 3
4 2
2 1


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
AB=[]
for _ in range(n):
    AB.append(list(map(int,input().split())))
dp=[0]+[float("INF")]*h
for i in range(1,h+1):
    for a,b in AB:
        if i<=a:
            dp[i]=min(dp[i],b)
        else:
            dp[i]=min(dp[i],b+dp[i-a])
print(dp[-1])

Submission status: Time Limit Exceeded

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

for i in range(n):
  a, b = map(int, input().split())
  monster[i][0], monster[i][1] = a, b

dps = [0 for i in range(h + 1)]
for i in range(1, h + 1):
  ans = 10 ** 10
  for m in monster:
    ans = min(ans, dps[max(i - m[0], 0)] + m[1])
  dps[i] = ans

print(dps[h])

Submission status: Time Limit Exceeded

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

ab_list = []

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

ma_list = [0]*h

for i in range(h):
    ma_list[i] = 10000000000
    for item in ab_list:
        ma = 0
        if item[0] >= (i + 1):
            ma = item[1]
        else:
            ma = item[1] + ma_list[i - item[0]]
        if ma_list[i] > ma:
            ma_list[i] = ma

print(ma_list[-1])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
l = []
dp = [987654321] * (h + 10001)
dp[0] = 0

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

for x in range(h + 1):
    for y in l:
        if dp[x + y[0]] > dp[x] + y[1]:
            dp[x + y[0]] = dp[x] + y[1]

print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

dp = [[float("inf")] * (h + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n + 1):
    dp[i][0] = 0

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

ans = dp[n][h]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

inf = float('inf')

h, n, *ab = map(int, sys.stdin.read().split())
ab = list(zip(*[iter(ab)] * 2))

def main():
    dp = [inf] * (h + 1)
    dp[0] = 0
    for i in range(1, h+1):
        for a, b in ab:
            dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        
    return dp[h]

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
    a_sub,b_sub=map(int,input().split())
    a.append(a_sub)
    b.append(b_sub)
inf=10000000000000
ma=max(a)
dp=[inf]*(h+1+ma)
dp[0]=0
for i in range(n):
    x=[a[i],b[i]]
    for j in range(h+1+ma):
        if dp[j]!=inf:
            if j+x[0]<=h+ma:
                dp[j+x[0]]=min(dp[j+x[0]],dp[j]+x[1])
            else:
                break
print(min(dp[h:]))
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
h,n= map(int, input().split())
m = {}
l = {}
for i in range(n):
  a,b = map(int, input().split())
  if b in m:
    if m[b] < a:
      m[b] = a
  else:
    m[b] = a
d = 0
i = 1
ans = []
while(d<h):
  d = 0
  if i in m:
    d = m[i]
  for j in m.keys():
    if i-j in l:
      d = max(d,l[i-j]+m[j])
  l[i] = d
  i += 1
print(i-1)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
import operator as op
from functools import reduce
import numpy as np
import math
import bisect
import heapq


MOD = 1000000007


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def main():
    H, N = get_inputs(int)
    A = np.empty(N, dtype=np.int32)
    B = np.empty(N, dtype=np.int32)
    for i in range(N):
        a, b = get_inputs(int)
        A[i] = a
        B[i] = b

    dp = np.zeros(H+1, dtype=np.int32)
    for h in range(1, H+1):
        # v = 1e7
        # for i in range(N):
        #     a = A[i]
        #     b = B[i]
        #     # v = min(v, dp[max(0, h-a):h].min() + b)
        #     v = min(v, dp[max(0, h-a)] + b)
        # dp[h] = v

        dp[h] = min([dp[max(0, h-a)] + b for a, b in zip(A, B)])
    print(dp[H])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MAX = 10**9 + 7


def main():
    H, N = map(int, input().split())
    damage_costs = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [MAX] * (H + 1 + max(damage_costs, key=lambda x: x[0])[0])
    dp[0] = 0

    for (ai, bi) in damage_costs:
        for i, dp_i in enumerate(dp):
            if i >= ai:
                dp[i] = min(dp_i, dp[i - ai] + bi)

    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,n=map(int,input().split())
a,b=[],[]
for _ in range(n):
    aa,bb=map(int,input().split())
    a.append(aa)
    b.append(bb)
a=np.array(a)
b=np.array(b)
dp=np.full((n+1,h+1),int(1e10),dtype=int)
dp[0,0]=0
for i in range(n):
    for j in range(h+1):
        dp[i+1][j] = min(dp[i,j], dp[i+1,max(0,j-a[i])]+b[i])
print(dp[n][h])

Submission status: Time Limit Exceeded

Solution code:
# ABC153e


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)

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

    # dp[i][j]=i番目までの魔法でモンスターの体力をj減らすためにつかう魔力の最小値
    # dp[i][j]=min(dp[i-1][j],dp[i][j-maho[i][0]])+maho[i][1]

    dp = [[10 ** 12] * (h + 1) for _ in range(3)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(h + 1):
            if j == 0:
                dp[(i + 1) % 3][0] = 0
            dp[(i + 1) % 3][j] = min(dp[i % 3][j],
                                     dp[(i + 1) % 3][max(0, j - maho[i][0])] + maho[i][1])
    print(dp[n % 3][h])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ini_A,ini_B = A[0], B[0]
dp = [-(-j//ini_A)*ini_B for j in range(H+1)]

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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

INF = 2 ** 64
dprint(INF)
dp = [INF] * (h + 10 ** 4)
dp[0] = 0

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

dprint(dp[:10])
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
h,n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

inf = 10**9
dp = [[inf]*(h+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(h+1):
        k = 0
        while ab[i][0]*k<=h:
            d = j+ab[i][0]*k
            dp[i+1][min(h,d)] = min(dp[i+1][min(h,d)], dp[i][j]+ab[i][1]*k)
            k += 1
        d = j+ab[i][0]*k
        dp[i+1][min(h,d)] = min(dp[i+1][min(h,d)], dp[i][j]+ab[i][1]*k)

res = dp[n][h]
print(res)

Submission status: Time Limit Exceeded

Solution code:
# ABC153e


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)

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

    # dp[i][j]=i番目までの魔法でモンスターの体力をj減らすためにつかう魔力の最小値
    # dp[i][j]=min(dp[i-1][j],dp[i][j-maho[i][0]])+maho[i][1]

    dp = [[10 ** 12] * (h + 1) for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(h + 1):
            if j == 0:
                dp[i + 1][0] = 0
            dp[i + 1][j] = min(dp[i][j],
                               dp[i + 1][max(0, j - maho[i][0])] + maho[i][1])
    print(dp[n][h])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

mh = [-1] * (h+1)
mh[0] = 0

for i in range(h+1):
    for j in range(n):
        if i - a[j] <= 0:
            cus = 0
        else:
            cus = mh[i - a[j]]
        if mh[i] == -1 or  cus + b[j] < mh[i]:
            mh[i] = cus + b[j]


print(mh[h])

Submission status: Time Limit Exceeded

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


def dp(H, memo):
    if H in memo:
        return memo[H]
    if H <= 0:
        return 0
    res = min(dp(H - a, memo) + b for a, b in AB)
    memo[H] = res
    return res

H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
memo = {}
print(dp(H, memo))

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int,input().split())
a,b = [],[]
for i in range(n):
    ta,tb = map(int,input().split())
    a.append(ta)
    b.append(tb)
    
dp = [[0 for j in range(h+1)] for i in range(n)]
for i in range(n):
    for j in range(1,h+1):
        if i == 0:
            dp[i][j] = dp[i][max(0,j-a[i])]+b[i]
        else:
            t1 = dp[i-1][j]
            t2 = dp[i-1][max(0,j-a[i])]+b[i]
            t3 = dp[i][max(0,j-a[i])]+b[i]
            dp[i][j] = min(t1,t2,t3)

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

dp = [123456789012] * (10**8 + 10)

dp[0] = 0
for i in range(h+1):
    if dp[i] == 123456789012:
        continue
    for j in range(n):
        dp[i+ab[j][0]] = min(dp[i+ab[j][0]],dp[i] + ab[j][1])
ans = 123456789012
for i in range(h,h+10000+2):
    ans = min(ans,dp[i])
print(ans)

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 = [[float('inf')]*(2*10**4+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

for i in range(N):
    for j in range(1,2*10**4+1):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-AB[i][0]]+AB[i][1])
        
ans = float('inf')
for i in range(H,2*10**4+1):
    ans = min(ans,dp[N][i])
print(ans)

Submission status: Time Limit Exceeded

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


def dp(H, memo={}):
    if H <= 0:
        return 0
    elif H in memo:
        return memo[H]
    res = min(dp(H - a, memo) + b for a, b in zip(A, B))
    memo[H] = res
    return res

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

print(dp(H))

Submission status: Time Limit Exceeded

Solution code:
import sys

h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = [INF] * (20201)
dp[0] = 0
for line in sys.stdin:
    a, b = map(int, line.split())
    for i in range(10000):
        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:
H, N = [int(s) for s in input().split()]
dec = []
cost = []
for i in range(N):
    a, b = [int(s) for s in input().split()]
    dec.append(a)
    cost.append(b)
memo = [None]*(H+1)
memo[0] = 0
for h in range(1,H+1):
    memo[h] = memo[max(0,h-dec[0])]+cost[0]
    for i in range(1,N):
        memo[h] = min(memo[h], memo[max(0,h-dec[i])]+cost[i])
print(memo[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):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
INF = 10**10
dp = [INF] * (H+1)
dp[0] = 0
for i in range(N):
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(0, j-A[i])]+B[i])
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**10] * (H+1)
DP[H] = 0
for h in range(H, 0, -1):
    for a, b in AB:
        x = max(0, h - a)
        DP[x] = min(DP[x], DP[h] + b)
print(DP[0])

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)

tables=[[0 for i in range(H+1)] for j in range(N+1)]
for i in range(1,H+1):
    tables[0][i]=10**10

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

print(tables[-1][-1])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

INF=10**9

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

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**9
    h,n=MI()
    aa=[]
    bb=[]
    for _ in range(n):
        a,b=MI()
        aa.append(a)
        bb.append(b)
    dp=[inf]*(h+1)
    dp[0]=0
    for i in range(h):
        pre=dp[i]
        for a,b in zip(aa,bb):
            ni=h if i+a>h else i+a
            if pre+b<dp[ni]:dp[ni]=pre+b
    print(dp[h])

main()

Submission status: Time Limit Exceeded

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

D=[1<<31]*(H+10**4)
D[0]=0

for hp in range(H):
    for a,b in M:
        D[hp+a]=min(D[hp+a],D[hp]+b)
print(min(D[H:]))

Submission status: Time Limit Exceeded

Solution code:
H,N = [int(i) for i in input().split()]
AB = [[int(i) for i in input().split()] for j in range(N)]
DP = [10000000000]*(H+1)#DP[h] = 体力をh削るのに必要な魔力のmin
DP[0] = 0
for h,curmp in enumerate(DP):
    for a,b in AB:
        goal = min(h+a,H)
        DP[goal] = min(DP[goal],curmp+b)
print(DP[-1])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import random
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

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

# dp[h]: 体力を h にするのに必要な魔力の合計の最小値
dp = [INF] * (H + 1)
dp[H] = 0
for a, b in AB:
    for h in reversed(range(H + 1)):
        dp[max(0, h - a)] = min(dp[h] + b, dp[max(0, h - a)])
print(dp[0])

Submission status: Memory Limit Exceeded

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

a=[]
b=[]
for _ in range(n):
    a1,b1=map(int,input().split())
    a.append(a1)
    b.append(b1)
for i in range(10**4+2):
    
    for j in range(n):
        dp[i+a[j]]=min((dp[i+a[j]]),dp[i]+b[j])
print(min(dp[h:]))

Submission status: Accepted

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

INF = 10**18
dp = [INF]*(h+1)
dp[h] = 0
for i in reversed(range(h+1)):
    for j in range(n):
        a,b = AB[j]
        if i-a >= 0:
            dp[i-a] = min(dp[i-a], dp[i]+b)
        else:
            dp[0] = min(dp[0], dp[i]+b)
print(dp[0])

Submission status: Accepted

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def ceil(x,p):
    if x%p==0:
        return x//p
    else:
        return x//p+1

def main():
    INF = 10**9
    h,n = map(int,input().split())
    spell = []
    for _ in range(n):
        spell.append(tuple(map(int,input().split())))

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

    for i,item in enumerate(spell):
        a,b = item
        for j in range(h):
            if j-a<0:
                dp[i+1][j+1] = min(dp[i][j+1],b*ceil(j+1,a))
            else:
                dp[i+1][j+1] = min(dp[i][j+1],dp[i+1][j+1-a]+b)
        
    print(dp[n][h])
main()

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  p=10005
  h,n=LI()
  a=[]
  b=[]

  for _ in range(n):
    x,y=LI()
    a.append(x)
    b.append(y)

  dp=[[inf]*(p+1) for _ in range(n+1)]
  dp[0][0]=0

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

  # print(dp)
  ans=inf
  for i in range(h,p+1):
    ans=min(ans,dp[n][i])
  return ans

# main()
print(main())

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  p=20010
  h,n=LI()
  a=[]
  b=[]

  for _ in range(n):
    x,y=LI()
    a.append(x)
    b.append(y)

  dp=[[inf]*p for _ in range(n+1)]
  dp[0][0]=0

  for i in range(n):
    for j in range(p-5):
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])
      if j+a[i]<p:
        dp[i+1][j+a[i]]=min(dp[i+1][j+a[i]],dp[i+1][j]+b[i])

  # print(dp)
  ans=inf
  for i in range(h,20010):
    ans=min(ans,dp[n][i])
  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
def getval():
    h,n = map(int,input().split())
    m = [list(map(int,input().split())) for i in range(n)]
    return h,n,m

def main(h,n,m):
    #DP for minimal mp needed to do h damage
    dp = [0]
    for i in range(h):
        update = 2**60
        for j in m:
            if j[0]>=(i+1):
                update = min(update,j[1])
            else:
                update = min(update,j[1]+dp[i+1-j[0]])
        dp.append(update)
    print(dp[h])    
                
if __name__=="__main__":
    h,n,m = getval()
    main(h,n,m)

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
INF = 10**9
dp= [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):
    if j+a > H:
      dp[H] = min(dp[H], dp[j] + b)
    else:
      dp[j+a] = min(dp[j+a], dp[j] + b)
print(dp[H])

Submission status: Accepted

Solution code:
# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# from collections import deque
# import heapq

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
H, N = map(int, input().split())
# A = list(map(int, input().split()))
# A = list(map(lambda x: int(x)*(-1), input().split()))
# B = list(map(int, input().split()))
A_B = [list(map(int,input().split())) for _ in range(N)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# edges = [list(map(int,input().split())) for _ in range(N - 1)]
# tree = [[] for _ in range(N + 1)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])

# depth = [-1] * (N + 1)
# depth[1] = 0
# count = [0] * (N + 1)

# for i in range(Q):
#     p, x = map(int, input().split())
#     count[p] += x

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + 1
#             dfs(tree, l[0])
# dfs(tree, 1)


# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr



# bfs
# tree = [[] for _ in range(N + 1)]
# edges = [list(map(int,input().split())) for _ in range(M)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])

# depth = [-1] * (N + 1)
# depth[1] = 0

# d = deque()
# d.append(1)

# ans = [0] * (N + 1)
# while d:
#  v = d.popleft()
#  for i in tree[v]:
#    if depth[i] != -1:
#      continue
#    depth[i] = depth[v] + 1
#    ans[i] = v
#    d.append(i)

# # ans = depth[2:]
# print('Yes')
# print(*ans[2:], sep="\n")

max_a = max(a for a, b in A_B)

max_damege = H + max_a

dp = [0] * (max_damege + 1)

for i in range(max_damege + 1):
    dp[i] = min(dp[i-a]+b for a,b in A_B)

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

Submission status: Accepted

Solution code:
h,n = map(int, input().split())
ab = []
amax = 10**5
for _ in range(n):
  ab.append(tuple(map(int,input().split())))
amax = max(a for a,b in ab)
p = [0]*(h+amax+1)
for i in range(1,h+amax):
  p[i] = min(p[i-a]+b for a,b in ab)
print(p[h])

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

dp = [float("inf") for i in range(10**5)]
dp[0] = 0

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
a=[0]
b=[0]
width=2*10**4+7
dp=[[10**10 for i in range(width)] for j in range(n+1)]
dp[0][0]=0
dp[1][0]=0
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
for i in range(1,n+1):
    for j in range(width):
        dp[i][j]=min(dp[i][j],dp[i-1][j])
        if(j+a[i]<width):
            dp[i][j+a[i]]=min(dp[i][j+a[i]],dp[i][j]+b[i])
print(min(dp[n][h:]))

Submission status: Accepted

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)

dp=[[float("inf")]*(H+1) for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
	a, b = A[i], B[i]
	for j in range(H+1):
		if a>=j:
			dp[i+1][j] = min(dp[i][j], b)
		else:
			dp[i+1][j] = min(dp[i][j], dp[i+1][j-a]+b)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
from functools import reduce

def main():
    H, N = MI()
    A = []
    B = []
    A_B = []
    for i in range(N):
        a, b = MI()
        A.append(a)
        B.append(b)
    max_A = max(A)
    #dp[i]=体力iを削るのに必要な最小魔力
    dp = [10 ** 9] * (H + max_A)
    dp[0] = 0
    for j in range(N):
        a_j = A[j]
        b_j = B[j]
        for i in range(H + max_A):
            if i - a_j >= 0:
                dp[i] = min(dp[i - a_j] + b_j, dp[i])
            else:
                dp[i] = min(b_j, dp[i])

    ans = min(dp[H:H + max_A])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(n):
    p,m = map(int,input().split())  
    P.append(p)
    M.append(m)
    
dp=[[999999999]*(h+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        dp[i+1][min(j+P[i],h)] = min(dp[i+1][min(j+P[i],h)],dp[i+1][j] + M[i] )
 
print(dp[n][h])

Submission status: Accepted

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

m = 20010
dp = [1000000000] * m
dp[0] = 0
for a, b in ab:
    for i in range(m):
        if i - a >= 0:
            dp[i] = min(dp[i], dp[i - a] + b)
print(min(dp[h:]))

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,N=MI()
    A=[0]*N
    B=[0]*N
    
    for i in range(N):
        A[i],B[i]=MI()
        
    inf =10**20
    dp=[[inf]*(H+1)for _ in range(N+1)]
    # dp[i]はi番目の魔法まででhpをj減らす方法
    
    dp[0][0]=0
    
    for i in range(N):
        a=A[i]
        b=B[i]
        for j in range(H+1):
            if j-a>=0:
                dp[i+1][j]=min(dp[i+1][j],
                               dp[i][j],
                               dp[i+1][j-a]+b)
            else:
                dp[i+1][j]=min(dp[i+1][j],
                               dp[i][j],
                               dp[i+1][0]+b)
                
    print(dp[-1][-1])

main()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,N=MI()
    A=[0]*N
    B=[0]*N
    
    for i in range(N):
        A[i],B[i]=MI()
        
    inf =10**20
    dp=[[inf]*(H+1)for _ in range(N+1)]
    # dp[i]はi番目の魔法まででhpをj減らす方法
    
    dp[0][0]=0
    
    for i in range(N):
        a=A[i]
        b=B[i]
        for j in range(H+1):
            dp[i+1][j]=min(dp[i+1][j],
                           dp[i][j])
            if j-a>=0:
                dp[i+1][j]=min(dp[i+1][j],
                               dp[i+1][j-a]+b)
            else:
                dp[i+1][j]=min(dp[i+1][j],
                               dp[i+1][0]+b)
                
    print(dp[-1][-1])

main()