问题 D: 硕鼠

问题 D: 硕鼠

时间限制: 1 Sec  内存限制: 128 MB
提交: 47  解决: 39
[提交][状态][讨论版][命题人:]

题目描述

胖老鼠准备了M磅的猫粮,准备和看守仓库的猫交易,仓库里有他最喜欢的食物,爪哇豆JavaBeans

这个仓库有n个房间。第i个房间含有J[i]磅的JavaBeans,需要F[i]磅的猫食。FatMouse不必交易房间里的所有JavaBean,相反,如果付给F[i]*a%磅的猫粮,他可能会得到J[i]*a%磅的JavaBeans。这里是一个实数。现在他把这项作业分配给你:告诉他他能得到的最大数量的JavaBeans。


FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.

输入

输入由多个测试用例组成。每个测试用例以包含两个非负整数M和N的行开始。然后N行跟随,每个行分别包含两个非负整数J[i]和F[i]。最后一个测试用例后面是两到1个,所有的整数都不大于1000。


The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.

输出

对于每个测试用例,在一行中打印一个实数,最多精确到小数点后3位,这是FatMouse可以获得的JavaBean的最大数量。


For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.

样例输入

5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

样例输出

13.333
31.500

提示


-李勇周赛

[提交][状态]