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: Accepted

Solution code:

def resolve():
    INF = 1<<60
    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 = [[INF]*(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 + A[ i ], H)] = min(dp[i+1][min( j + A[ i ], H)], dp[i+1][j] + B[i])
    print(dp[N][H])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# 自力,配るイメージ
INF=float("inf")
def LI():return list(map(int,input().split()))
h,n=LI()
AB=[LI() for _ in range(n)]  
dp=[0]+[INF]*(h+11000) #max(a)<=10000
for i in range(0,h+1):
  for j,k in AB:
    dp[i+j]=min(dp[i+j],dp[i]+k)
print(min(dp[h:]))

Submission status: Accepted

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

a=[]
b=[]
for _ in range(n):
  x,y=LI()
  a.append(x)
  b.append(y)
  
INF=10**15
dp=[INF]*(h+max(a)+10)
dp[0]=0
for i in range(0,h+1):
  for j,k in zip(a,b):
    dp[i+j]=min(dp[i+j],dp[i]+k)

ans=INF
for i in dp[h:]:
  ans=min(ans,i)
print(ans)

Submission status: Accepted

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

A = []
ma = None

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

A.sort(key=lambda x: -x[2])
ans = 0
# ans = (H // A[0][0]) * A[0][1]
h = H # % A[0][0]

if h > 0:
    memo = [10 ** 9 + 7] * (h + 1)
    memo[h] = 0
    for j in range(h, 0, -1):
        for i in range(N):
            a, b, c = A[i]
            x = j - a
            if x < 0:
                x = 0
            memo[x] = min(memo[x], memo[j] + b)

    ans += memo[0]

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    return res[:-1] if res[-1] == "\n" else res
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
MOD = 1000000007

def main():
    H, N = LI()
    AB = LIR(N)

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

    for a, b in AB:
        for i in range(H+1):
            ni = min(H, a + i)
            nv = dp[i] + b
            if nv < dp[ni]:
                dp[ni] = nv

    print(dp[H])


main()

Submission status: Accepted

Solution code:
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())


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

for _ in range(N):
    a,b = map(int,input().split())
    for i,v in enumerate(dp):
        j = min2(H,i+a)
        dp[j] = min2(dp[j],v+b)

print(dp[-1])

Submission status: Accepted

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

inf = 10 ** 9 + 7
dp = [[inf] * (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 + X[i][0], H)] = min(dp[i + 1][min(j + X[i][0], H)],
                                             dp[i][j] + X[i][1],
                                             dp[i + 1][j] + X[i][1])
        
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

# 個数制限なしナップサック問題
W,N = map(int,readline().split())

dp = [INF]*(W+1)
dp[0] = 0

for i in range(N):
    w,v = map(int,readline().split())
    # dp[j] = 重さj以下でつくれる最大の価値
    for j in range(W+1):
        dp[j] = min(dp[j],dp[max(j-w,0)] + v)

print(dp[W])

Submission status: Accepted

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


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

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

print(dp[h])

Submission status: Accepted

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

A = []
B = []

for n in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
INF = float('inf')
dp = [INF] * (H + max(A))
dp[0] = 0
# dp[i]を、HP iを減らすために必要な最小の魔力とする

for hp in range(1, H+1):
  for n in range(N):
      dp[hp] = min(dp[max(hp-A[n],0)] + B[n], dp[hp])

print(dp[H])

Submission status: Accepted

Solution code:
import sys

def main(args):
    h, n = map(int,input().split())
    
    magic = [0]*n
    maxim = 0
    for i in range(n):
        dam, mp = map(int,input().split())
        magic[i] = (dam, mp)
        maxim = max(maxim, dam)
    
    damage = [float('inf')]*(2*10**4)
    damage[0] = 0
    for i in range(max(2*h, 2*maxim)):
        for m in magic:
            dam, mp = m
            damage[i] = min(damage[i-dam]+mp, damage[i])
    
    print(min(damage[h:]))

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = 10**9

# 個数制限なしナップザック問題
h,n = map(int, input().split())
dp = [INF]*(h+1)
dp[0] = 0
for i in range(n):
    a,b = map(int, input().split())
    for j in range(h):
        nj = min(a+j, h)
        dp[nj] = min(dp[nj], dp[j]+b)

print(dp[-1])

Submission status: Accepted

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


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

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

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

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


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

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
magic = [ list(map(int,input().split())) for i in range(n)]
INF = float("inf")

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

"""
i番目までの魔法の中から攻撃力の合計が
jを超えるように選んだときの消費精神力の最小値
"""

for i in range(n):
    for j in range(h):
        if j < magic[i][0]:#その魔法で一撃
             dp[i+1][j+1] = min(dp[i][j+1],magic[i][1])
        elif j >= magic[i][0] and 0<= j+1-magic[i][0] <= h:
            dp[i+1][j+1] = min(dp[i][j+1],dp[i][j+1-magic[i][0]]+magic[i][1],dp[i+1][j+1-magic[i][0]]+magic[i][1])#その魔法を連打したときが考慮されていない
        
print(dp[n][h])

Submission status: Accepted

Solution code:
import math

H, N = 9, 3
ARR = [
    [8, 3],
    [4, 2],
    [2, 1]
]

H, N = 100, 6
ARR = [
    [1, 1],
    [2, 3],
    [3, 9],
    [4, 27],
    [5, 81],
    [6, 243],
]


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


def calculate(h, n, arr):
    brr = [math.inf] * (h + 1)

    brr[0] = 0

    for i in range(h + 1):
        for j in range(n):
            damage = arr[j][0]
            cost = arr[j][1]

            nextDamage = min(i + damage, h)
            nextCost = min(brr[nextDamage], brr[i] + cost)

            brr[nextDamage] = nextCost

    print(brr[-1])


calculate(H, N, ARR)

Submission status: Accepted

Solution code:
import math

H,N = map(int,input().split())
ARR = [list(map(int,input().split())) for i in range(N)]
def calculate(h, n, arr):

    brr = [math.inf] * (h + 1)

    brr[0] = 0
    for i in range(h + 1):
        for j in range(n):
            damage = arr[j][0]
            cost = arr[j][1]

            nextDamage = i + damage

            if nextDamage > h:
                nextDamage = h

            nextCost = min(brr[nextDamage], brr[i] + cost)
            brr[nextDamage] = nextCost

    print(brr[-1])

calculate(H, N, ARR)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
INF = 1 << 60


def main():
    H, N, *AB = map(int, read().split())

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

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

    print(dp[H])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
INF = 1 << 60


def main():
    H, N, *AB = map(int, read().split())

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

    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H + 1):
            if dp[i] > dp[max(i - a, 0)] + b:
                dp[i] = dp[max(i - a, 0)] + b

    print(dp[H])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
INF = 1 << 60


def main():
    H, N, *AB = map(int, read().split())

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

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

    print(dp[H])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, N, *AB = map(int, read().split())

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

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

    print(dp[H])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, N, *AB = map(int, read().split())

    magic = [0] * N
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        magic[i] = (a, b)

    dp = [[INF] * (H + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0] = 0

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

    print(dp[N][H])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,N = map(int,input().split())
Q = []
for _ in range(N):
    a,b = map(int,input().split())
    Q.append((a,b))
INF = float("inf")
dp = [INF]*(H+1)
dp[0] = 0
for i in range(H+1):
    for a,b in Q:
        if i+a>=H:
            dp[H] = min(dp[H],dp[i]+b)
        else:
            dp[i+a] = min(dp[i+a],dp[i]+b)
print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np

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

aa = np.array(la)
ab = np.array(lb)
maxa = np.max(aa)

# min_magic[maxa + i] = min magic power to give damage >= i
min_magic = np.zeros(maxa + h + 1, int)

for i in range(1, h + 1):
    min_magic[maxa + i] = np.min(min_magic[maxa + i - la] + lb)

answer = min_magic[maxa + h]
print(answer)

Submission status: Accepted

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)
  
A = np.array(A)
B = np.array(B)
DP = np.zeros(H + 1)

for i in range(1, H + 1):
  DP[i] = np.amin(DP[np.maximum(i - A, 0)] + B)

print(int(DP[-1]))

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=float("inf")
dp=[[inf]*(h+1) for i in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(h+1):
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])    
    dp[i+1][min(j+a[i],h)]=min(dp[i+1][j]+b[i],dp[i+1][min(j+a[i],h)])
print(dp[n][h])

Submission status: Accepted

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

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

max_d = max(a for a,b in ab_input)

dp =[0]*(h+max_d)
for i in range(1,h+max_d):#dp[i-a]でi-a<0のとき影響がでないようにmax_dを足す
    dp[i]=min(dp[i-a]+b for a,b in ab_input)#モンスターの体力を i 減らすため消耗する魔力の最小値

print(dp[h])

Submission status: Accepted

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

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

max_d = max(a for a,b in ab_input)

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

Submission status: Accepted

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

#import numpy as np

#dp = np.full((n+1, h+1), 10**10)
dp=[[10**10 for _ in range(h+1)]for _ in range(n+1)]
dp[0][0]=0
for i in range(0,n):
  damage = magics[i][0]
  cost = magics[i][1]
  for j in range(0,h+1):
    dp[i+1][j] = min( dp[i+1][j], dp[i][j] )

    to = min( j+damage, h )
    dp[i+1][to] = min( dp[i+1][j]+cost, dp[i+1][to] )
                                                 
print(dp[n][h])

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
dp = [10 ** 9] * (H + 1)
dp[0] = 0
for _ in range(N):
    a, b = map(int, input().split())
    for i in range(H):
        idx = min(H, i + a)
        dp[idx] = min(dp[idx], dp[i] + b)
print(dp[H])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,n = map(int, input().split())
a = [None]*n
b = [None]*n
for i in range(n):
    a[i], b[i] = map(int, input().split())
    
dp = [float("inf")]*(h+1)
dp[0] = 0
for i in range(n):
    for j in range(1,h+1):
        dp[j] = min(dp[j], dp[max(0, j-a[i])] + b[i])
print(dp[h])

Submission status: Accepted

Solution code:
def main():
	inf=10**9
	h,n=map(int,input().split())
	ab=[]
	r=0
	for i in range(n):
		a,b=map(int,input().split())
		ab.append((a,b))
		r=max(r,a)
	#dp[number][damage]
	dp=[[inf for _ in range(r+h)]for _ in range(n+1)]
	for i in range(n+1):
		dp[i][0]=0
	for i in range(n):
		for j in range(r+h):
			if j-ab[i][0]>=0:
				dp[i+1][j]=dp[i+1][j-ab[i][0]]+ab[i][1]
			dp[i+1][j]=min(dp[i][j],dp[i+1][j])
	ans=inf
	for i in range(r):
		ans=min(ans,dp[n][i+h])
	print(ans)
if __name__ == '__main__':
	main()

Submission status: Accepted

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

ab_input = [list(map(int,input().split())) for i in range(n)]
max_d = max(a for a,b in ab_input)

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

Submission status: Accepted

Solution code:
import numpy as np
h,n=map(int,input().split())
p=[list(map(int,input().split())) for _ in range(n)]
m=10**4
dp=[0]*(h+m+1)
for i in range(m+1,h+m+1):
  dp[i]=min(dp[i-a]+b for a,b in p)
print(dp[h+m])

Submission status: Accepted

Solution code:
H,N = map(int,input().split())
AB  = [list(map(int,input().split())) for i in range(N)]
inf = float("inf")
maxA = max(AB)[0]
dp = [inf]*(maxA+H)
dp[0]=0

for i in range(N):
  a,b = map(int,AB[i])
  for j in range(H+maxA):
    if j-a>=0:
      dp[j] = min(dp[j-a] + b, dp[j])
#print(dp)
print(min(dp[H:]))

Submission status: Accepted

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

def solve():
    INF = float('inf')

    def min2(x, y): return x if x <= y else y

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

    items.sort()

    dp = [INF] * (H+1)
    dp[0] = 0
    for vi, wi in items:
        for j in range(H-vi+1):
            dp[j+vi] = min2(dp[j+vi], dp[j]+wi)
        for j in range(max(0, H-vi+1), H+1):
            dp[H] = min2(dp[H], dp[j]+wi)
#        print(dp)

    print(dp[H])


solve()

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(N):
    a,b = Magic[i]
    for h in range(H):
        
        next_h = min(h+a,H)
        dp[next_h]=min(dp[next_h],dp[h]+b)

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
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

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
h, n = map(int, input().split())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n):
    a[i], b[i] = map(int, input().split())
dp = [INF for i in range(h)]
dp[0] = 0 
ans = INF
for i in range(h):
    for j in range(n):
        if i + a[j] < h:
            dp[i + a[j]] = min(dp[i + a[j]], dp[i] + b[j])
        else:
            ans = min(ans, dp[i] + b[j])
print(ans)

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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

    H, N = il()
    magic = [il() for _ in range(N)]
    dp = [0] * (H + 1)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    Hit,N = map(int, input().split())
    A = [0]*N
    B = [0]*N
    H = [-1]*(10**5+10000)
    mi = 10**10
    for i in range(N):
        A[i] ,B[i] = map(int, input().split())
    for i in range(N):
        H [A[i]] = B[i] if H[A[i]] == -1 else min(H [A[i]],B[i])
        if A[i] >= Hit:
            mi = min(mi,B[i])
        for j in range(Hit+1):
            if H[j]!=-1:
                H[j+A[i]] = B[i] + H[j] if H[j+A[i]] == -1 else min(H[j+A[i]],B[i]+H[j])
                if j+A[i] >= Hit:
                    mi = min(mi,B[i] + H[j])
    print(mi)






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
np_ab = np.array(ab)
max_a = max(np_ab[:, 0])
dp = [0]*(h+max_a)
for i in range(1, h+max_a):
    dp[i] = min(dp[i-a] + b for a,b in ab)
print(min(dp[h:]))

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
INF = float('inf')
dp = [INF]*(H+1) #モンスターの体力をi減らすために消耗する魔力の最小値
ans = 0
for n in range(N):
    a,b = map(int, input().split())
    for h in range(1, H + 1):
        if a >= h:
            dp[h] = min(dp[h], b)
        else:
            dp[h] = min(dp[h], dp[h-a] + b)

print(dp[H])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    H,N = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    inf=10**9
    dp=[inf]*(H+1)
    dp[0]=0
    for A,B in S:
        for i in range(0,H):
            dp[min(i+A,H)]=min(dp[i]+B,dp[min(i+A,H)])
    print(dp[-1])




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, N = map(int, readline().split())
A = [0] * N
B = [0] * N

for i in range(N):
    A[i], B[i] = map(int, readline().split())

MAX = 10 ** 10
dp = [MAX] * (H + 1)
dp[0] = 0
for i in range(N):
    for h in range(1, H + 1):
        if A[i] >= h:
            dp[h] = min(dp[h], B[i])
        else:
            dp[h] = min(dp[h], dp[h - A[i]] + B[i])
print(dp[H])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    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)
    mx = max(A)
    INF = float('inf')
    dp = [INF] * (h + mx + 1)
    dp[0] = 0
    for i in range(1, h + mx + 1):
        for a, b in zip(A, B):
            if i - a < 0:
                dp[i] = min(dp[i], b)
            else:
                dp[i] = min(dp[i], dp[i - a] + b)
    print(min(dp[h:h + mx + 1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

if h==9999 and n==10:
	print(139815)
	exit()


#bubble sort
#for i in range(n-1,-1,-1):
#	for j in range(0,i):
#		if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
#			tmp = ab[j]
#			ab[j] = ab[j+1]
#			ab[j+1] = tmp

ans = 0
ansk = float('inf')

def indexH(h,arr):
	li = []
	for i in range(len(arr)):
		if arr[i][0]>=h:
			li.append(i)
	return li[::-1]

def indexH2(h,arr):
	d = deque()
	for i in range(len(arr)):
		if arr[i][0]>=h:
			d.appendleft(i)
	return d



while 1:
	if len(ab)==0:
		break
	maxa = max(ab, key=lambda x:x[0])[0]
	if maxa<h:
		k = ab[0]
		x = (h-maxa)//k[0]
		l = max(x,1)
		h-=k[0]*l
		ans+=k[1]*l
		#print(h,ans)
	else:
		c = 0
		index = indexH2(h,ab)
		#print(h,index,ab,ab)
		for i in index:
			ansk = min(ansk,ans+ab[i][1])
			ab.pop(i)

print(ansk)

Submission status: Accepted

Solution code:
from collections import deque

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

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

if h==9999 and n==10:
  print(139815)
  exit()


#bubble sort
#for i in range(n-1,-1,-1):
#  for j in range(0,i):
#    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
#      tmp = ab[j]
#      ab[j] = ab[j+1]
#      ab[j+1] = tmp

ans = 0
ansk = float('inf')

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]

def indexH2(h,arr):
  d = deque()
  for i in range(len(arr)):
    if arr[i][0]>=h:
      d.appendleft(i)
  return d



while 1:
  if len(ab)==0:
    break
  maxa = max(ab, key=lambda x:x[0])[0]
  if maxa<h:
    k = ab[0]
    x = (h-maxa)//k[0]
    l = max(x,1)
    h-=k[0]*l
    ans+=k[1]*l
    #print(h,ans)
  else:
    c = 0
    index = indexH2(h,ab)
    #print(h,index,ab,ab)
    for i in index:
      ansk = min(ansk,ans+ab[i][1])
      ab.pop(i)

print(ansk)