hdu1009.c

/*
   hdoj 1009
   @author: chm

*/

#include <stdio.h>
#include <stdlib.h>

struct T
{
    int cfood, jbean;
    double ratio;
} room[10086];

int cmp(const void* a, const void* b)
{
    struct T* p1 = (struct T*)a;
    struct T* p2 =  (struct T*)b;
    return p2->ratio > p1->ratio ? 1 : -1;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
#endif

    int  m, n;

    while (scanf("%d%d", &m, &n) != EOF && !(m == -1 && n == -1))
    {
        int i;
        for (i = 0; i < n; ++i)
        {
            scanf("%d%d", &room[i].jbean, &room[i].cfood);
            room[i].ratio =  room[i].jbean * 1.0 / room[i].cfood;
        }
        qsort(room, n, sizeof(room[0]), cmp);
        double tot = 0.0;
        for (i = 0; i < n; ++i)
        {
            if (m < room[i].cfood)      //get at most as we can 
            {
                tot += m * room[i].ratio;
                break;
            }
            else                        //get all jbeans
            {
                tot += room[i].jbean;
                m -= room[i].cfood;
            }
        }

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

    return 0;
}