## page was renamed from 程序设计练习16——zju2109——FatMouse' Trade
= FatMouse' Trade =

http://acm.zju.edu.cn/show_problem.php?pid=2109

Time limit: 1 Seconds 

Memory limit: 32768K

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.

== Input ==
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.

== Output ==
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.

== Sample Input ==
{{{5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1}}}

== Sample Output ==
{{{13.333
31.500}}}


------

{{{#!cplusplus
/*Written by czk*/
#include <iostream>
#include <iomanip>
#include <queue>
using namespace std;
struct room{
	int java_bean;
	int cat_food;
	bool operator<(const room &r) const{
		return static_cast<double>(java_bean) / cat_food < static_cast<double>(r.java_bean) / r.cat_food;
	}
};

int main() {
	while(1) {
		int m, n;
		cin >> m >> n;
		if (m == -1 && n == -1) break;
		priority_queue<room> rooms;
		for(int i = 0; i < n; i++) {
			room r;
			cin >> r.java_bean >> r.cat_food;		
			rooms.push(r);
		}
		double total = 0.0;
		while(!rooms.empty() && m > 0) {
			if(m>rooms.top().cat_food) {
				total += rooms.top().java_bean;
				m -= rooms.top().cat_food;
			} else {
				total += static_cast<double>(rooms.top().java_bean) / rooms.top().cat_food * m;
				m = 0;
			}
			rooms.pop();
		}
		cout << fixed<<setprecision(3) << total  << endl;
	}

}
}}}