题目描述

宿舍四个人又在玩求生之路2！大家正在对付tank。

tank的血量为 H，现在有 N 种枪，第 i 种枪射击一次会造成 A[i] 点伤害，耗用 B[i] 颗子弹。

当tank的血量小于等于 0 时就击败了它。

由于后面还会有一大波尸群来袭，所以需要你求出最少使用多少子弹可以击败tank。

注：每种枪可以使用任意次。

输入

第一行两个整数 H,N。（1 ≤ H ≤ 10000，1 ≤ N ≤ 1000） 后 N 行每行两个整数 A[i],B[i]。(1 ≤ A[i],B[i] ≤ 10000)

输出

一个整数，表示所需最少的子弹数。

示例

input

7 3
3 5
9 12
4 6

output

11

解释

可以发现，使用第一把和第三把枪各射击一次，可以击败tank，且消耗子弹最少。

限制

时间限制：1s 空间限制：128 MB