7371: 打怪兽 1
[Creator : ]
Description
有一只怪兽的血量为 $H$。
你现在有 $N$ 个技能，编号为 $1 \sim N$。技能 $i$ 可以对怪兽造成 $A_i$ 点伤害，但是需要 $B_i$ 点魔力值。
问你最少需要多少点魔力值，可以杀死该怪兽，其血量小于等于 0 即为死亡。
每个技能可以重复使用。
你现在有 $N$ 个技能，编号为 $1 \sim N$。技能 $i$ 可以对怪兽造成 $A_i$ 点伤害，但是需要 $B_i$ 点魔力值。
问你最少需要多少点魔力值，可以杀死该怪兽，其血量小于等于 0 即为死亡。
每个技能可以重复使用。
Input
第一行包括两个整数 $H,N$。
其后 $2 \sim N+1$ 行，每行两个整数 $A_i, B_i$。
其后 $2 \sim N+1$ 行，每行两个整数 $A_i, B_i$。
Output
最少需要多少点魔力值，可以杀死该怪兽。
Constraints
$1 \leq H \leq 10^4$
$1 \leq N \leq 10^3$
$1 \leq A_i, B_i \leq 10^4$
$1 \leq N \leq 10^3$
$1 \leq A_i, B_i \leq 10^4$
Sample 1 Input
9 3
8 3
4 2
2 1
Sample 1 Output
4
Sample 2 Input
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
Sample 2 Output
139815