朱鹮对怪兽 - 代码源竞赛平台

题目描述

蜗蜗正在与一只生命值为 $H$ 的怪兽战斗。他会使用 $N$ 种魔法：第 $i$ 种魔法对怪兽造成 $A_i$ 点伤害，同时消耗 $B_i$ 点魔力。

每种魔法都可以使用任意次，除此之外没有其他伤害怪兽的方法。当怪兽的剩余生命值降到 $0$ 或以下时，蜗蜗获胜。最后一次魔法造成的伤害可以超过怪兽剩余生命值。

求蜗蜗获胜所需消耗的最少魔力。

输入格式

第一行包含两个整数 $H,N$，分别表示怪兽的初始生命值和魔法种数。

接下来 $N$ 行，每行包含两个整数 $A_i,B_i$，表示一种魔法的伤害和魔力消耗。

输出格式

输出一行一个整数，表示获胜所需的最少魔力。

样例

10 2
6 5
4 4

9

9 2
6 4
3 3

7

样例解释

样例 1 中，分别使用一次两种魔法，可造成 $6+4=10$ 点伤害，消耗 $5+4=9$ 点魔力。

样例 2 中，分别使用一次两种魔法，可造成 $6+3=9$ 点伤害，消耗 $4+3=7$ 点魔力。

数据范围

对于 100% 的数据，保证 $1\le H\le 10^4$，$1\le N\le 10^3$，$1\le A_i,B_i\le 10^4$。