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 = map(int, input().split() )

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

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

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

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

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: 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)
# process
dp = np.zeros(H+1, dtype=np.int64)
dp[0] = 0

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

# output
print(dp[H])

Submission status: Accepted

Solution code:
import sys
import numpy as np
 
h, n = map(int, 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)

#k番目の魔法を最後に使って合計iのダメージを与える時の魔力消費量は、
#min(i-Akダメージの魔力消費量)+Bk
#iダメージ与える最小消費量を、上記計算式を全ての1<=k<=nで探索
#1<=i<=hでforを繰り返して、hダメージ与える最小魔力消費量を算出

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

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
#print(l)
weight=[0]*n
value=[0]*n
for i in range(n):
    weight[i],value[i]=l[i][0],l[i][1]
w=h
#print(weight,value)
dp=[[float('inf')]*(w+1) for i in range(n+1)]
for i in range(n):
    for j in range(1,h+1):
        if j<=weight[i]:
            dp[i+1][j]=min(dp[i][j],value[i])
        elif j>=weight[i]:
            dp[i+1][j]=min(dp[i+1][j-weight[i]]+value[i],dp[i][j])
    #print(dp[:i+2])
print(dp[n][w])

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

AB = [list(map(int, input().split())) for _ in range(N)]
A, B = np.array(AB, dtype=np.int64).reshape(N, 2).T

# process
dp = np.zeros(H+1, dtype=np.int64)
dp[0] = 0

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

# output
print(dp[H])

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
a, b = zip(*(list(map(int, input().split())) for _ in range(N)))
maxA = max(a)

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

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

print(min(dp[H:]))

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
a, b = zip(*(list(map(int, input().split())) for _ in range(N)))
maxA = max(a)

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

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

print(min(dp[H:]))

Submission status: Accepted

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

for i in range(h + 1):
    for damage, mp in ab:
        rep = INF
        if (0 <= (i - damage)):
            rep = dp[i - damage] + mp
        else:
            rep = mp
        dp[i] = min(dp[i], rep)
print(dp[h])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

Submission status: Accepted

Solution code:
#モンスターの体力は H
#トキはN種類の魔法が使え、
#i番目の魔法を使うと、モンスターの体力を Ai減らすことができますが、
#トキの魔力を Bi消耗します。

#dp[i] = モンスターの体力を i 減らすため消耗する魔力の最小値
#dp[i+1] = min(dp[i-Ai]+Bi,dp[i])
#dp[0]=0

h, n = map(int, input().split())
dp=[10**8]*(10**5+1)

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

for i in range(1,h+1):
  for j in range(0,n):
    if i-ab[j][0]<=0:
      x=ab[j][1]
    else:
      x=dp[i-ab[j][0]]+ab[j][1]
    dp[i]=min(dp[i],x)
print(dp[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] = map(int, input().split())

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

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

Submission status: Accepted

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

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

print(dp[h])

Submission status: Accepted

Solution code:
H,N=map(int, input().split())
A=[list(map(int, input().split())) for i in range(N)]
maxa=max(a for a,b in A)
DP=[0]*(H+maxa)
for i in range(0,H+maxa):
  if i<=0:
    DP[i]=0
  else:
    DP[i]=min(DP[i-a]+b for a,b in A)
print(min(DP[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=[1000000000]*(H+max(A)+1)
DP[0]=0


for i in range(N):
    DP[A[i]]=B[i]

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

print(min(DP[H:]))

Submission status: Accepted

Solution code:
import sys

H, N = map(int, input().split())
M = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]
# A = [0] * N
# B = [0] * N
# for i, (a, b) in enumerate(M):
#     A[i] = a
#     B[i] = b


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

for i in range(H):
    for j in range(N):
        ni = min(H, i + M[j][0])
        b = M[j][1]
        dp[ni] = min(dp[ni], dp[i] + b)

print(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 i in range(N)])
A = AB[:, 0]
B = AB[:, 1]

dp = np.array([0]*(H+1))

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

print(dp[-1])

Submission status: Accepted

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

Submission status: 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)]

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

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


main()

Submission status: Accepted

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

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

Submission status: Accepted

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

inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for _ in range(N):
    A, B = map(int, input().split())
    for i in range(H):
        t1 = i + A
        if t1 > H:
            t1 = H
        t2 = dp[i] + B
        if t2 < dp[t1]:
            dp[t1] = t2
print(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 = [0] * (h+max_a)

for i in range(0,h+max_a):
    if i==0:
        dp[i]=0
    else:
        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 = [0] * (h+max_a)

for i in range(0, h+max_a):
    if i <= 0:
        dp[i] = 0
    else:
        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())
spells = [tuple(map(int,input().split())) for _ in range(N)]
max_a = max(spells)[0]

dp = [0]
for i in range(1, H + max_a + 1):
  try:
    dp.append(min([dp[i - a] + b for a,b in spells if a <= i]))
  except ValueError:
    dp.append(10**8)

print(min(dp[H:]))

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

    max_A = max(a for a, _ in AB)
    inf = float('inf')
    dp = [inf] * (H + max_A + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == inf:
            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:
import math
 
h,n=map(int,input().split())
a=[0]*n
b=[0]*n
for i in range(n):
    a[i],b[i]=list(map(int,input().split()))
 
 
dp=[[b[0]] * (h+1) for i in range(n+1)]
for j in range(h+1):
    dp[0][j]=math.ceil(j/a[0])*b[0]
for i in range(n):
    for j in range(h+1):
        if j<a[i]: dp[i+1][j]=min(dp[i][j],b[i])
        else:dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i]]+b[i])
print(dp[n][h])

Submission status: Accepted

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

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

    print(dp[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, N = map(int, input().split())
INF = 10 ** 12

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

dp = [INF for j in range(H+10**4+1)]
dp[0] = 0

for i in range(N):
    for j in range(1, H+10**4+1):
        if j - M[i][0] >= 0:
            dp[j] = min(dp[j], dp[j-M[i][0]] + M[i][1])

ans = INF
for i in range(10**4+1):
    ans = min(ans, dp[H+i])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np


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


H, N = inpl()
AB = [inpl() for i in range(N)]

A, B = np.array(AB, dtype=np.int64).reshape(N, 2).T

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

print(dp[H])

Submission status: Accepted

Solution code:
def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h+1111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

def main():
  def dp(i):
    for a,b in AB:
      T=C[i-a if i>a else 0]+b
      C[i]=T if T<C[i] else C[i]

  H,N=map(int,input().split())
  AB=[list(map(int,input().split())) for _ in range(N)]
  C=[0]+[10**8]*H

  for i in range(1,H+1):
    dp(i)

  print(C[H])

if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left
INF = float('inf')

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

hm = list(list(map(int, input().split())) for i in range(N))

for i in range(1, H+1):
    dp[i] = min(list(dp[i - h] + m for h, m in hm))
print(dp[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] = map(int, input().split())

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

dp[0][0] = 0

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

        dp[i+1][nj] = min(dp[i][nj], dp[i+1][j] + B[i])

print(dp[N][H])

Submission status: Accepted

Solution code:
from sys import stdin

h,n = [int(x) for x in stdin.readline().rstrip().split()]
a = [0]*n
b = [0]*n

for i in range(n):
    a[i],b[i] = [int(x) for x in stdin.readline().rstrip().split()]

#最高で削られる可能性がある体力
H = max(a)

inf = 10**10

#体力をちょうどi削るために必要な最低の魔力
dp = [inf for _ in range(h+H+1)]
dp[0] = 0

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

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)]
memo = [10**10]*(H+1)
memo[0] = 0
i = 0
while i <= H:
  for a, b in AB:
    memo[i] = min(memo[i], b+memo[max(0, i-a)])
  i += 1
print(memo[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 + 10 ** 4)

dp[0] = 0
for j in range(H + 10 ** 4):
    for i in range(N):
        dp[j] = min(dp[j], dp[max(0, j - A[i])] + B[i])
print(min(dp[H:]))

Submission status: Accepted

Solution code:
import sys

lines = sys.stdin.readlines()

H, M = list(map(int, lines[0].split()))
AB = []

max_at = 0
min_mg = sys.maxsize
at_min_mg = 0
for i in range(M):
  t = tuple(map(int, lines[i+1].split()))
  AB.append(t)
  if t[0]>=max_at:
    max_at = t[0]
  if t[1]<=min_mg:
    min_mg = t[1]
    at_min_mg = t[0]

ABlen = len(AB)

DP = [0]
for i in range(1, at_min_mg+1):
  DP.append(min_mg)
  
for i in range(at_min_mg+1,H+max_at+1):
  mm = sys.maxsize
  for j in range(ABlen):
    if i-AB[j][0]<0:
      continue
    if mm > DP[i-AB[j][0]]+AB[j][1]:
      mm = DP[i-AB[j][0]]+AB[j][1]
  DP.append(mm)
print(min(DP[H:H+max_at]))

Submission status: Accepted

Solution code:
import sys
import functools


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


@functools.lru_cache(maxsize=None)
def solve(h):
    if h <= 0:
        return 0

    ret_val = float("inf")
    for a, b in AB:
        val = b + solve(h - a)
        if val < ret_val:
            ret_val = val
        else:
            break
    return ret_val


sys.setrecursionlimit(100000)

H, N = inpl()
AB = [inpl() for i in range(N)]
AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
# print(AB)
print(solve(H))

Submission status: Accepted

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

#dp[v]:体力をv減らす時の最小魔力
dp=[10**20 for i in range(h+1)]
dp[0]=0

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

        else:
            dp[i]=min(dp[i],dp[i-x[j][0]]+x[j][1])
print(dp[-1])

Submission status: Accepted

Solution code:
#H = int(input())
H,N = list(map(int,input().split()))
#H = sorted(list(map(int,input().split())))
AB = [list(map(int,input().split())) for i in range(N)]
dp = [float('inf') for i in range(H)]
dp[0] = 0
for i in range(N):
    for j in range(H):
        if j-AB[i][0] >= 0:
            dp[j] = min(dp[j],dp[j-AB[i][0]]+AB[i][1])
ans = float('inf')
for i in range(N):
    for j in range(max(0,H-AB[i][0]),H):
        if dp[j] != float('inf') and j+AB[i][0] >= H:
            ans = min(ans,dp[j]+AB[i][1])
print(ans)

Submission status: Accepted

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

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

# dp = [[None] * n for _ in range(h + 1)]
#
# def dfs(at, i):
#     at = max(at, 0)
#
#     if dp[at][i] is not None:
#         return dp[at][i]
#
#     if i == n - 1:
#         r = ((at + ab[i][0] - 1) // ab[i][0]) * ab[i][1]
#     elif at <= 0:
#         r = 0
#     else:
#         r = min(dfs(at - ab[i][0], i) + ab[i][1], dfs(at, i + 1))
#
#     dp[at][i] = r
#     return r
#
# print(dfs(h, 0))

dp = [[0] * n for _ in range(h + 1)]
i = n - 1
for at in range(h + 1):
    dp[at][i] = ((at + ab[i][0] - 1) // ab[i][0]) * ab[i][1]

for at in range(h + 1):
    for i in reversed(range(n - 1)):
        r = min(
            dp[max(0, at - ab[i][0])][i] + ab[i][1],
            dp[at][i + 1])
        dp[at][i] = r
print(dp[h][0])

Submission status: Accepted

Solution code:
#H = int(input())
H,N = list(map(int,input().split()))
#H = sorted(list(map(int,input().split())))
AB = sorted([list(map(int,input().split())) for i in range(N)])
dp = [float('inf') for i in range(H)]
dp[0] = 0
for j in range(H):
    for i in range(N):
        if j-AB[i][0] >= 0:
            dp[j] = min(dp[j],dp[j-AB[i][0]]+AB[i][1])
ans = float('inf')
for i in range(N):
    for j in range(max(0,H-AB[i][0]),H):
        if dp[j] != float('inf') and j+AB[i][0] >= H:
            ans = min(ans,dp[j]+AB[i][1])
print(ans)

Submission status: Accepted

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

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

dg = 10**5

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

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

d[0] = 0

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

print(d[-1])

Submission status: 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)
  
BIG = 10**8+1
dp = [BIG for i in range(2*10**4+1)]
dp[0] = 0
for i in range(H+1):
    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())
magic = []
for i in range(N):
    a,b = map(int,input().split())
    magic.append([a,b])

INF = 10**9
DP = [INF]*(20005); DP[0] = 0

for i in range(1,20005):
    h = INF
    for j in range(N):
        if i - magic[j][0] >= 0:
            k = magic[j][1] + DP[i - magic[j][0]]
        else:
            k = magic[j][1]
        h = min(h,k)
    DP[i] = h

ans = DP[H]
for i in DP[H+1:]:
    ans = min(ans,i)
print(ans)

Submission status: Accepted

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

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

for i in range(1, H+1):
    for atk, mp in M:
        if i - atk > 0:
            dp[i] = min(dp[i], dp[i-atk]+ mp)
        else:
            dp[i] = min(dp[i], mp)

print(dp[H])

Submission status: Accepted

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

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

INF = 1 << 60
dp = [INF for _ in range(h+10001)]

dp[0] = 0

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

res = INF
for i in range(h, h+10001):
    res = min(res, dp[i])
print(res)

Submission status: Accepted

Solution code:
import sys


def solve(h, n, ab):
    ab.sort(key=lambda x: x[1] / x[0])
    INF = 10 ** 18
    cache = {}
    # とりあえず一番コスパいいやつだけを使った結果を暫定最良値としておく
    best = ((h - 1) // ab[0][0] + 1) * ab[0][1]

    def dp(k, i=0, cost=0):
        nonlocal best
        if k <= 0:
            return cost
        if (k, i) in cache:
            return cache[k, i] + cost
        a, b = ab[i]
        if k / a * b + cost >= best:
            # どう足掻いても残りでbestより良い結果は得られない
            return INF
        c = (k - 1) // a + 1
        if i == n - 1:
            ret = cost + b * c
        else:
            ret = min(dp(k - a * j, i + 1, cost + b * j) for j in range(c + 1))
        cache[k, i] = ret - cost
        best = min(best, ret)
        return ret

    dp(h)
    return best


sys.setrecursionlimit(10001)

h, n = map(int, input().split())
ab = [tuple(map(int, line.split())) for line in sys.stdin]
print(solve(h, n, ab))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
'''
# 以下はTLである
H, N = map(int, input().split())
magic = []
# Aは威力Bは消費魔力
for i in range(N):
    A, B = map(int, input().split())
    magic.append([A,B])

# DPで解く
# DP[i]ダメージをi与えた時の最低使用魔力
# DP[H]ダメージがH以上になったときの最低使用魔力
# DP[i] = -1 のときは計算しない
DP = [-1 for _ in range(H+1)]
DP[0] = 0

for i in range(H):
    if DP[i] == -1:
        pass
    else:
        for j in range(N):
            h = i + magic[j][0]
            mp = DP[i] + magic[j][1]
            if h <= H and DP[h] == -1:
                DP[h] = mp
            elif h <= H and DP[h] != -1:
                if DP[h] > mp:
                    DP[h] = mp
            elif h > H and DP[H] == -1:
                DP[H] = mp
            elif h >H and DP[H] != -1:
                if DP[H] > mp:
                    DP[H] = mp

#print(DP)
print(DP[H])
'''


'''
# 改善しているがこれもTL
# おそらく関数のappendが足を引っ張っている
def test_func(dp, A_list, B_list, i, N):
    # 参考return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))
    magic = []
    for j in range(N):
        # 考えたいiに対してその元となるdpが存在するか
        if i >= A_list[j]:
            magic.append(dp[i-A_list[j]] + B_list[j])
        # 初めての
        else:
            magic.append(B_list[j])
    # 一番魔力がかからなかったものを採用する
    return min(magic)

H, N = map(int, input().split())
A_list = []
B_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)

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

for i in range(1,H+1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

print(dp[H])
'''

def test_func(dp, A_list, B_list, i, N):
    return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))
    '''
    # 最初から配列に格納
    magic = []
    for j in range(N):
        # 考えたいiに対してその元となるdpが存在するか
        if i >= A_list[j]:
            magic.append(dp[i-A_list[j]] + B_list[j])
        # 初めての
        else:
            magic.append(B_list[j])
    # 一番魔力がかからなかったものを採用する
    return min(magic)
    '''
H, N = map(int, input().split())
A_list = []
B_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)

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

for i in range(1,H+1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

print(dp[H])

Submission status: Accepted

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

h, n = map(int, input().split())
abc = []

for _ in range(n):
    a, b = map(int, input().split())
    c = a / b
    abc.append((c, a, b))

abc.sort(reverse=True)

dp = [0] * (h + 1)

c, a, b = abc[0]
temp = a
m = 0
while 1:
    m += b
    if temp >= h:
        dp[h] = m
        break
    else:
        dp[temp] = m
    temp += a

if n == 1:
    print(dp[h])
    exit()

for c, a, b in abc[1:]:
    if a < h:
        if dp[a] == 0:
            dp[a] = b
        else:
            dp[a] = min(dp[a], b)
    for i in range(1, h):
        if dp[i] != 0:
            if i + a >= h:
                dp[h] = min(dp[h], dp[i] + b)
            elif dp[i+a] == 0:
                dp[i+a] = dp[i] + b
            else:
                dp[i+a] = min(dp[i+a], dp[i] + b)

print(dp[h])

Submission status: Accepted

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

# 一次元で可能
dp = [10**10 for _ in range(h+1)]
dp[0] = 0

for damage, cost in magic:
    for j in range(h+1):
        nj = min(j+damage, h)
        dp[nj] = min(dp[nj], dp[j]+cost)

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