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.

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.

CHEN, Yue

 /**

  * acm.hdu.edu.cn

  * Problem#1009

  * Accepted

  * Time:46ms

  * Memory:1596k

  */

 #include<iostream>

 #include<cstdio>

 #include<cctype>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<fstream>

 #include<sstream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 #include<stack>

 using namespace std;

 typedef bool boolean;

 #define INF 0xfffffff

 #define smin(a, b) a = min(a, b)

 #define smax(a, b) a = max(a, b)

 template<typename T>

 inline void readInteger(T& u){

     char x;

     int aFlag = ;

     while(!isdigit((x = getchar())) && x != '-');

     if(x == '-'){

         x = getchar();

         aFlag = -;

     }

     for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');

     ungetc(x, stdin);

     u *= aFlag;

 }

 typedef class Data{

     public:

         int f;

         int j;

         double b;

 }Data;

 int n, m;

 Data* datas;

 inline boolean init() {

     readInteger(n);

     readInteger(m);

     if(n == - && m == -)    return false;

     datas = new Data[(const int)(m + )];

     for(int i = ; i <= m; i++){

         readInteger(datas[i].j);

         readInteger(datas[i].f);

         datas[i].b = datas[i].j * 1.0 / datas[i].f;

     }

     return true;

 }

 boolean cmpare(const Data& a, const Data& b){

     return a.b > b.b;

 }

 double result;

 inline void solve() {

     result = 0.0;

     sort(datas + , datas + m + , cmpare);

     int i = ;

     while(n >=  && i <= m){

         int buy = min(n, datas[i].f);

         if(buy == datas[i].f)    result += datas[i].j;

         else    result += buy * 1.0 / datas[i].f * datas[i].j;

         n -= buy;

         i++;

     }

     printf("%.3lf\n", result);

 }

 int main(){

     while(init()){

         solve();

         delete[] datas;

     }

     return ;

 }