http://acm.hdu.edu.cn/showproblem.php?pid=1009

简单的贪心法。。。。

//HDOJ 1009 Code By NetBeans 6.9.1
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct ROOMTYPE
{
    double J, F, average;
};

bool cmp( ROOMTYPE x, ROOMTYPE y );

int main()
{
    int M, N;
    while( cin >> M >> N && M != -1 && N != -1 )
    {
        ROOMTYPE room[N];
        for( int i = 0; i < N; i++ )
        {
            cin >> room[i].J >> room[i].F;
            room[i].average = room[i].J / room[i].F;
        }
        sort( room, room + N, cmp );
        double sum = 0;
        for( int i = 0; i < N && M > 0; i++ )
        {
            if( M >= room[i].F )
            {
                sum += room[i].J;
                M -= room[i].F;
            }
            else
            {
                sum += M / room[i].F * room[i].J;
                M = 0;
            }
        }
        printf( "%.3f\n", sum );
    }
    return 0;
}

bool cmp( ROOMTYPE x, ROOMTYPE y )
{
    return x.average > y.average;
}
#if gongzi
#endif