← 返回题目列表

AtCoder · abc153_e

E. 朱鹮 vs 怪物

中文机器翻译题面 查看原题

分数: 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