王道论坛计算机考研机试指南六贪心算法-简书(王道论坛计算机考研)

例2.11
fatmouse
（九度教程第21题）

时间限制：1秒
**内存限制：32兆 **
特殊判题：否

题目描述：
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 t

he maximum amount of javabeans he can obtain.

输入：
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.

输出：
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