# AtCoder Beginner Contest 153

URL: https://atcoder.jp/contests/abc153 (opens new window)

# E

h,n = gets.chomp.split(" ").map(&:to_i)
arr = n.times.map{gets.chomp.split(" ").map(&:to_i)}

# 体力iのモンスターを倒すための最小魔力
dp = Array.new(h+1, 10 ** 8)
dp[0] = 0

arr.each do |(a, b)|
  1.upto(h) do |i|
    tmp = 0
    # 前回までの攻撃
    tmp += dp[i - a] if i - a >= 0
    # 今回の攻撃
    tmp += b
    dp[i] = [dp[i], tmp].min
  end
end

puts dp[-1]
Last Updated: 2020/08/09 18:33