分数: 500 点
问题陈述
宜必思正在与怪物战斗。
的 健康 该怪物的 是 H.
宜必思可以施放 N 各种法术。铸造 i-第一个法术会降低怪物的生命值 A_i,代价是 B_i 魔法点。
同一法术可以施展多次。除了法术之外,没有其他方法可以降低怪物的生命值。
当怪物的生命值变为 0 或以下。
找出获胜前必须消耗的最低总魔法点。
约束
- 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
H N A_1 B_1 : A_N B_N
输出
打印获胜前必须消耗的最低总魔法点。
示例输入 1
9 3 8 3 4 2 2 1
示例输出 1
4
首先,让我们施放第一个法术来减少怪物的生命值 8,代价是 3 魔法点。怪物现在的生命值是 1.
然后,施放第三个咒语,使怪物的生命值减少 2,代价是 1 魔点。怪物现在的生命值是 -1.
这样,我们就能以总成本赢得胜利 4 魔法点。
示例输入 2
100 6 1 1 2 3 3 9 4 27 5 81 6 243
示例输出 2
100
施放第一个法术是最佳选择 100 次。
示例输入 3
9999 10 540 7550 691 9680 700 9790 510 7150 415 5818 551 7712 587 8227 619 8671 588 8228 176 2461
示例输出 3
139815