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:
h, n = (int(x) for x in input().split())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
dp = [0] * (h + max(a for a, _ in ab))
for i in range(1, h + 1):
    dp[i] = min(dp[i - a] + b for a, b in ab)
print(dp[h])

Submission status: Accepted

Solution code:
h, n = (int(x) for x in input().split())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
max_a = max(a for a, _ in ab)
dp = [0] * (h + max_a)
for i in range(1, h + 1):
    dp[i] = min(dp[i - a] + b for a, b in ab)
print(dp[h])

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(1000000)

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 ab: (ab[0] / ab[1], -ab[0]), reverse=True)


@lru_cache(maxsize=None)
def solve(h):
    if h <= 0:
        return 0
    best = float("inf")
    for a, b in AB:
        val = b + solve(h - a)
        if val < best:
            best = val
        else:
            break
    return best


print(solve(H))

Submission status: Accepted

Solution code:
def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [10**18 for _ in range(H + max_a)]
    dp[0] = 0

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, _ in ab)
dp = [0]*(H+max_a)
for i in range(1,H+1):
  dp[i] = min(dp[i-a]+b for a,b in ab)
print(dp[H])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
inf = 10**10
magic = [list(map(int,input().split())) for i in range(n)]
max_a = max(a for a,b in magic)
dp = [inf for i in range(h + max_a)]
dp[0] = 0
for i in range(1,h+max_a):
    dp[i] = min(dp[i-a] + b for a,b in magic)
print(min(dp[h:]))

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
now = [10**10 for _ in range(h+1)]
now[0] = 0
for _ in range(n):
  a,b = map(int,input().split())
  for i in range(1,h+1):
    if i - a >= 0:
      now[i] = min(now[i],now[i-a]+b)
    else:
      now[i] = min(now[i],b)
print(now[-1])

Submission status: Accepted

Solution code:
import numpy as np
 
h, n = map(int, input().split())
a = []
b = []
for _ in range(n):
  ai, bi = map(int, input().split())
  a.append(ai)
  b.append(bi)
a = np.array(a)
b = np.array(b)
dp = np.zeros(h+1, dtype=np.int)
for c in range(1, h+1):
  dp[c] = np.min(dp[np.maximum(0, c-a)] + b)
print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np
h, n = map(int, input().split())    
ab = np.array([tuple(map(int, input().split())) for _ in range(n)])
dp = np.zeros(h + 1, dtype="int")
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i - ab[:, 0], 0)] + ab[:, 1])
print(dp[-1])

Submission status: Accepted

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

inf=10**9
dp=[[0]+[inf]*hp for i in range(n+1)]
for i in range(n):
  damage=magics[i][0]
  cost=magics[i][1]
  for j in range(hp+1):
    if j<damage:
      dp[i+1][j]=min(dp[i][j],cost)
    else:
      dp[i+1][j]=min(dp[i][j],(dp[i+1][j-damage]+cost))
print(dp[n][hp])

Submission status: Accepted

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


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

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

DP = []
for _ in range(n + 1):
    DP.append([0] + [float("inf")] * h)

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

print(DP[n][h])

Submission status: Accepted

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

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

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]
ma=max(a for a,b in A)
dp=[0]*(h+ma)
for i in range(1,h+ma):
  dp[i]=min(dp[i-a]+b for a,b in A)
print(min(dp[h:]))

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',"""
h,n=[int(j) for j in input().split()]
ab=[[int(j) for j in input().split()] for i in range(n)]
dp=[10**18]*(h+1)
dp[0]=0
ans=10**18
for a,b in ab:
    for i in range(h+1):
        if dp[i]!=10**18:
            if i+a<h:
                if dp[i]+b<dp[i+a]:
                    dp[i+a]=dp[i]+b
            else:
                if dp[i]+b<ans:
                    ans=dp[i]+b
 
print(ans)

"""))

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())

maxi=max(A)
DP=[0]*(H+maxi)
DP[0]=0

for i in range(1,H+maxi):
  mini=float("inf")
  for j in range(N):
    if i-A[j]>=0:
      mini=min(mini, DP[i-A[j]]+B[j])
  DP[i]=mini
  
mini2=float("inf")
for k in range(H,H+maxi):
  mini2=min(mini2,DP[k])

print(mini2)

Submission status: Accepted

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

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

amax = max(a for a,b in ls)

dp = [0]*(h+amax)

for i in range(1,h+amax):
  p = max(1,2)
  dp[i] = min(dp[i-a]+b for a,b in ls)

print(min(dp[h:]))

Submission status: Accepted

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

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

amax = max(a for a,b in ls)

dp = [0]*(h+amax)

for i in range(1,h+amax):
  dp[i] = min(dp[i-a]+b for a,b in ls)

print(min(dp[h:]))

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * (h+1) for _ in range(n+1)]
for j in range(1, h+1): dp[0][j] = float("inf")

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(0, j-a)] + b)

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

Submission status: Accepted

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

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for x in range(1, H + max_damage):
    dp[x] = min(dp[x - damage] + cost for damage, cost in magic)

print(min(dp[H:]))

Submission status: Accepted

Solution code:
import numpy as np

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

a, b = ab[:, 0], ab[:, 1]
dp = np.zeros(h+1, dtype=np.int)
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i-a, 0)] + b)

print(dp[h])

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
 
import itertools
 
#import bisect
 
import copy
from functools import lru_cache
 
def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result
 
def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta
 
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
 
#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
 
 
 
def main():
    h,n=map(int,input().split()) #n yen, m types
    ab=[list(map(int,input().split())) for i in range(n)]
    maxa = max(a for a, b in ab)
    dp=[INFI for i in range(h+maxa)]
    dp[0]=0
 
 
    def f(h):
 
        for a,b in ab:
            for j in range(h+maxa):
                dp[j]=min(dp[j],dp[j-a]+b)
        return min(dp[h:])
 
    print(f(h))
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
 
import itertools
 
#import bisect
 
import copy
 
 
def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result
 
def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta
 
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
 
#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
 
 
 
def main():
    h,n=map(int,input().split()) #n yen, m types
    a=[]
    b=[]
    for i in range(n):
        x,y=map(int,input().split())
        a.append(x)
        b.append(y)
 
    dp=[INFI for i in range(h+1)]
    dp[0]=0
    for i in range(n):
        for j in range(len(dp)):
            if j-a[i]<0:
                dp[j] = min(dp[j], dp[0] + b[i])
            else:
                dp[j]=min(dp[j],dp[j-a[i]]+b[i])
 
    print(dp[h])
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

  dp = [10 ** 8 + 1 for i in range(h + 10 ** 4 + 1)]
  dp[0] = 0

  for i in range(h):
    if dp[i] == 10 ** 8 + 1:
        continue
    for a, b in l:
      x = dp[i] + b
      if dp[i + a] > x:
        dp[i + a] = x

  print(min(dp[h:]))

main()

Submission status: Accepted

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

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1])

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

print(dp[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)

h,n=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
AB = [tuple(map(int, input().split())) for _ in range(n)]
#効率順にソート
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))

@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float('inf')
        for a, b in AB:
            mp = b + dp(h -a)
            if mp < best:
                best = mp
            else:
                break
        return best

print(dp(h))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
h, n = [int(i) for i in sys.stdin.readline().split()]
ls = []
INF = 10**9
for i in range(n):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    ls.append([a, b])
memo_ls = [[INF for j in range(h+1)] for i in range(n+1)]
memo_ls[0][0] = 0
for i, (a, b) in enumerate(ls, 1):
    for j in range(h+1):
        memo_ls[i][j] = min(memo_ls[i][max(0, j-a)] + b, memo_ls[i-1][j])
print(memo_ls[-1][-1])

Submission status: Accepted

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

# モンスターの体力をi、dp[i]を魔力の最小値とする
dp = [10**9]*(H+1)
# 正確にやるなら一番小さい魔力値で与えられるダメージより小さいiはその魔力値とした方がよさそう
dp[0] = 0

# 各魔法は何度同じのを使ってもよいので、1回のループではそれだけしか使わないパターンでやってみる
# それを各ループで同じdp配列を更新して、何度同じのを使ってもよいという状態を実現する
for i in range(N):
    a, b = ab[i]
    for j in range(H):
        # 残り体力 + 与えるダメージ
        k = min(j + a, H)
        # そのときの魔力最小値と、今回のダメージ与える前の魔力 + 使用魔力で小さい方を新たな魔力最小値とする
        dp[k] = min(dp[k], dp[j] + b)

print(dp[H])

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,n = LI()
    ab = [LI() for _ in range(n)]
    r = [inf] * (h+10**4+2)
    r[0] = 0
    for a,b in ab:
        for i in range(h):
            t = r[i] + b
            if r[a+i] > t:
                r[a+i] = t

    return min(r[h:])


print(main())

Submission status: Accepted

Solution code:
import numpy as np

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

a, b = ab[:, 0], ab[:, 1]
dp = np.zeros(h+1, dtype=np.int)
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i-a, 0)] + b)

print(dp[h])

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
H,N=map(int,input().split())
L=[[0,0]]#なんで最初に[0,0]を入れておくのか
for i in range(N):
    a,b=map(int,input().split())
    L.append([a,b])
INF=10**9

#dp[i][j]:iまでの魔法を使ってjダメージ与える場合の最小コスト
dp=[[INF for i in range(H+1)] for j in range(N+1)]
#print(dp)

#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):
        dp[i][j]=min(dp[i-1][j],dp[i][max(j-L[i][0],0)] + L[i][1])
print(dp[N][H])

Submission status: Accepted

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)

DP=[[0]*(H+1) for i in range(N)]
DP.insert(0,[float("inf")]*(H+max(A)))
DP[0][0]=0

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

print(DP[N][H])

Submission status: Accepted

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)

DP=[[0]*(H+max(A)) for i in range(N)]
DP.insert(0,[10**8+1]*(H+max(A)))
DP[0][0]=0

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

print(DP[N][H])

Submission status: Accepted

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)

DP=[[0]*(H+max(A)) for i in range(N)]
DP.insert(0,[10**8+1]*(H+max(A)))
DP[0][0]=0

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

print(DP[N][H])

Submission status: Accepted

Solution code:
import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('e1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()

inf = 10 ** 20

def solve():
    H, n = read_int_list()
    a, b = [0] * n, [0] * n
    for i in range(n):
        a[i], b[i] = read_int_list()
    cost = [0] * (H+1)
    for h in range(1, H+1):
        c = inf
        for i in range(n):
            health = h - a[i]
            if health < 0:
                health = 0
            if c > cost[health] + b[i]:
                c = cost[health] + b[i]
        cost[h] = c

    # for h in range(H + 1):
    #     print('\t', h, cost[h], file=sys.stderr)

    return cost[H]



def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def wczytaj_liste():
    ciag = input()
    rozdzielona_lista = ciag.split()
    odp = []
    for wyraz in rozdzielona_lista:
        liczba = int(wyraz)
        odp.append(liczba)
    return odp

def rzucanie_zaklenc(zycie, lista_zaklenc):
    koszt_zaklenc = [10**9] * (zycie+1)
    koszt_zaklenc[0] = 0
    for damage, cost in lista_zaklenc:
        for i in range(zycie+1):
            if i - damage >= 0:
                if cost+koszt_zaklenc[i-damage]< koszt_zaklenc[i]:
                    koszt_zaklenc[i] = cost+koszt_zaklenc[i-damage]
            else:
                if cost < koszt_zaklenc[i]:
                    koszt_zaklenc[i] = cost
    return koszt_zaklenc[zycie]

def E():
    H, N = wczytaj_liste()
    zaklencia = []
    for i in range(N):
        damage, cost = wczytaj_liste()
        zaklencia.append((damage, cost))
    print(rzucanie_zaklenc(H, zaklencia))

E()

Submission status: Accepted

Solution code:
import sys

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

dp = [float('inf') for _ in range(H + max(AB)[0] + 1)]
dp[0] = 0
for h in range(H + max(AB)[0] + 1):
    for n in range(N):
        if h - AB[n][0] >= 0:
            dp[h] = min(dp[h - AB[n][0]] + AB[n][1], dp[h])

print(min(dp[H:]))

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
L = []
for i in range(n):
  l = list(map(int,input().split()))
  L.append(l)
dp = [10**8]*10001
dp[0] = 0
for i in range(n):
  dp[L[i][0]] = L[i][1]
for i in range(10001):
  for j in range(n):
    if i-L[j][0] >= 0:
      dp[i] = min(dp[i],dp[i-L[j][0]]+L[j][1])
for i in range(9999,-1,-1):
  if dp[i] > dp[i+1]:
    dp[i] = dp[i+1]
print(dp[h])

Submission status: Accepted

Solution code:
import math

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

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

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

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

    print(dp[-1])

main()

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

print(int(dp[H]))

Submission status: Accepted

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

max_a = max(a for a, _ in ab)
dp = [10 ** 18 for _ in range(h + max_a)]
dp[0] = 0
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())
ab=[list(map(int,input().split())) for _ in range(n)]
max_a=max(a for a, _ in ab)
dp=[10**18 for _ in range(h+max_a)]
dp[0]=0
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:
import math
h,n = map(int,input().split())


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

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

for i in range(1, len(dp)):
    '''
    tmp = dp[i]
    for j in range(n):
        tmp = min(tmp, dp[max(0, i-a[j])] + b[j])
    dp[i] = tmp
    '''
    dp[i] = min(dp[i - A] + B for A, B in zip(a, b))

print(min(dp[h:]))

Submission status: Accepted

Solution code:
# i番目の重みws[i], 価値vs[i]
def solve(N, W, ws, vs):
    dp = [float("inf")] * (W + 1)
    dp[0] = 0
    for i in range(N):
        # 価値v, 重さw
        v = vs[i]
        w = ws[i]
        for j in range(w, W + 1):
            dp[j] = min(dp[j - w] + v, dp[j])
    return dp


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

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


dp = solve(n, h+10**4+1, ws, vs)

print(min(dp[h:]))

Submission status: Accepted

Solution code:
import sys

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

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

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

print dp[H]

Submission status: Accepted

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

def main2(H, N, AB):
    inf = 2**31 -1
    dp = [inf] * (H + max(a for a, _ in AB))
    dp[0] = 0
    for i in range(1, len(dp)):
        dp[i] = min(dp[i-a]+b for a,b in AB)
    print(min(dp[H:]))

main2(H,N,AB)

Submission status: Accepted

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)
#dp[i]=x  ダメージi与えるのに必要な魔力x　答えはdp[h]
INF=10**10
dp=[INF]*(10**5+5)
dp[0]=0
for i in range(h+max(A)+2):
  m=dp[i]
  for j in range(n):
    if i-A[j]<0:
      continue
    a=dp[i-A[j]]+B[j]
    if a<m:
      m=a
  dp[i]=m
  for j in range(i+1,i+1-max(A)-3,-1):
    if dp[j]>dp[j+1]:
      dp[j]=dp[j+1]
print(dp[h])

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 = [1e9]*(h+1)
dp[h]=0
for i in range(h+1):
    now=h-i
    if dp[now]==1e9:
        continue
    for j in range(n):
        now2=max(now-a[j],0)
        dp[now2]=min(dp[now2],(dp[now]+b[j]))
print(dp[0])

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 = [0]*(h+1)
for i in range(h+1):
    dp[i]=1000000000
dp[h]=0
for i in range(h+1):
    now=h-i
    if dp[now]==1e9:
        continue
    for j in range(n):
        now2=max(now-a[j],0)
        dp[now2]=min(dp[now2],(dp[now]+b[j]))
print(dp[0])

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 = [0]*(h+1)
for i in range(h+1):
    dp[i]=1000000000
dp[h]=0
for i in range(h+1):
    now=h-i
    for j in range(n):
        now2=max(now-a[j],0)
        dp[now2]=min(dp[now2],(dp[now]+b[j]))
print(dp[0])

Submission status: Accepted

Solution code:
def solve(h, n, AB):
    size = h + max(a for a, _ in AB) # 残りHP:1の時に最大火力を出すときまで考える
    dp = [-1] * size
    dp[0] = 0
    for i in range(1, size):
        # if 1撃で倒せる then b消費 else (HPがi-aのときの最小魔力+b)消費
        dp[i] = min(b if a >= i else dp[i - a] + b for a, b in AB)
    return min(dp[h:])

_h, _n = map(int, input().split())
_AB = [list(map(int, input().split())) for _ in range(_n)]
print(solve(_h, _n, _AB))

Submission status: Accepted

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

dp=[10**8+1 for i in range(h+1)]
dp[0]=0

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

print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np

h, n = map(int, raw_input().split())
a = np.zeros(n, dtype=int)
b = np.zeros(n, dtype=int)
for i in range(n):
    a[i], b[i] = map(int, raw_input().split())
dp = np.zeros(10001, dtype=int)
for i in range(1, 10001):
    dp[i] = (dp[i - a] + b).min()
print(dp[h])

Submission status: Accepted

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

DP = [10**9]*(H+1)
DP[0] = 0
for a,b in magic:
    for i in range(min(a,H+1)):
        DP[i] = min(DP[i],b)
    for i in range(a,H+1):
        DP[i] = min(DP[i],DP[i-a]+b)
print(DP[-1])

Submission status: Accepted

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

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

for i in range(1, len(dp)):
    for x, y in ab:
        if i - x > 0:
            dp[i] = min(dp[i], dp[i - x] + y)
        else:
            dp[i] = min(dp[i], y)

print(dp[h])

Submission status: Accepted

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

max_damage = max(A)
dp = [0 for _ in range(H + max_damage)]
for i in range(1, H + max_damage):
    dp[i] = min(dp[i - a] + b for a, b in zip(A, B))

print(min(dp[H:]))

Submission status: Accepted

Solution code:
INF = 10000000000
a=[0 for i in range(int(1e5))]
b=[0 for i in range(int(1e5))]
ans = [INF for i in range(int(1e5))]

def main():
    h,n = map(int,input().split())
    for i in range(n):
        tmp = list(map(int,input().split()))
        a[i] = tmp[0]
        b[i] = tmp[1]
        index = min(h,a[i])
        if b[i] < ans[index]:
            ans[index] = b[i]
    
    
    for i in range(h):
        if ans[i]!=INF:
            for j in range(n):
                index = min(h,a[j]+i)
                if ans[i]+b[j] < ans[index]:
                    ans[index] = ans[i]+b[j]
    print(ans[h])
if __name__=="__main__":
    main()

Submission status: Accepted

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

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

h, N = gets()
AB = getss(N)

dp = [0] + [float('inf')] * h
for a, b in AB:
    for i in range(h):
        j = min(i + a, h)
        dp[j] = min(dp[j], dp[i] + b)
print(dp[h])

Submission status: Accepted

Solution code:
import sys
import numpy as np

h, n = map(int, raw_input().split())
ab = np.array(sys.stdin.read().split(), dtype=np.int64)
aaa = ab[0::2]
bbb = ab[1::2]

dp = np.zeros(10001, dtype=np.int64)
for i in range(1, h + 1):
    dp[i] = (dp[i - aaa] + bbb).min()
print(dp[h])


# https://atcoder.jp/contests/abc153/submissions/9776226

Submission status: Accepted

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

h, N = gets()
AB = getss(N)

dp = [0] + [float('inf')] * h
for a, b in AB:
    for i in range(h):
        j = min(i + a, h)
        dp[j] = min(dp[j], dp[i] + b)
print(dp[h])

Submission status: Accepted

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

a = [0]*N
b = [0]*N

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

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

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