La pizza degli Hamtaro

La numerosa famiglia degli Hamtaro, composta da N criceti, ha prenotato un tavolo in una nota pizzeria.
I membri si danno appuntamento presso un autonoleggio con M automobili a disposizione per raggiungere successivamente la pizzeria.
Purtroppo gli Hamtaro non arrivano al volante e quindi devono pagare generosamente l’unico autista a disposizione dell’autonoleggio in quel momento.
Nell’ambiente dei cartoni gli Hamtaro sono notoriamente dei taccagni e vogliono perciò spendere il meno possibile per la serata, pena il passare la cena a pianger miseria.

Ogni automobile ha solo il carburante necessario per un viaggio autonoleggio-pizzeria-autonoleggio e non esistono distributori di carburante in zona: per cui dopo un viaggio con un’automobile i, l’automobile i rimane a secco e non può più essere usata.

L’automobile i permette il trasporto di P_i membri della famiglia degli Hamtaro, al costo di E_i euro per criceto.
Gli Hamtaro scelgono, ad ogni partenza, un’automobile tra quelle disponibili (tra quelle, cioè, non usate precedentemente) e l’autista la usa per accompagnare una parte di loro in pizzeria.

Aiuta la famiglia a risparmiare indicandole qual è la minima cifra che dovrà spendere per far arrivare tutti gli N Hamtaro in pizzeria!

Dati in Input

Il file input.txt contiene sulla prima riga i due interi positivi N e M, separati da uno spazio.
Le successive M righe (per i = 1, 2, …, M) contengono ciascuna due numeri interi positivi separati da uno spazio, a rappresentare il costo per criceto e la capacità dell’automobile: il primo intero indica E_i mentre il secondo intero indica P_i.

Dati in Output

Il programma, dopo aver letto il file di input, deve scrivere una sola riga nel file output.txt contenente un intero positivo che rappresenta la minima quantità di denaro necessaria per far arrivare tutti gli Hamtaro in pizzeria.

Assunzioni

1. 1 ≤ N ≤ 4000
2. 1 ≤ M ≤ 4000
3. 1 ≤ E_i ≤ 1000
4. 1 ≤ P_i ≤ 1000
5. È sempre possibile portare tutti gli Hamtaro in pizzeria.

Esempi di input/output

/*
    www.valcon.it  
    OII 2004 - Olimpiadi nazionali - LA PIZZA DEGLI HAMTARO
*/

#include
#include

typedef struct { int Euro, Portata; } automobile;

int cmp(const void *a1, const void *a2)
{  
    automobile A1=*((automobile*) a1);
    automobile A2=*((automobile*) a2);
    
    return A1.Euro-A2.Euro;
}

int main()
{
    int   N,                    /* numero criceti      */
          M;                    /* numero automobili   */
    automobile leAuto[4000];    /* parco auto con caratteristiche */
    int   i;
  
    FILE* fin =fopen( "input.txt", "r");
    FILE* fout=fopen("output.txt", "w");
  
    fscanf(fin, "%d %d", &N, &M);
    for(i=0; i < M; i++)
        fscanf(fin, "%d %d", &(leAuto[i].Euro), &(leAuto[i].Portata));

    qsort(leAuto, M, sizeof(automobile), cmp);  

    int  totPortati=0;
    long totEuro   =0;   
    int  numAuto   =0;
    while(totPortati < N)
    {    
        totPortati += leAuto[numAuto].Portata;
        totEuro    += leAuto[numAuto].Portata*leAuto[numAuto].Euro;
        numAuto++;
    }
    if(totPortati > N)
    {      
        numAuto--;
        totEuro -= (totPortati-N)*leAuto[numAuto].Euro;
    }
    
    fprintf(fout, "%ld", totEuro);
    return 0;
}