Algoritmi e Strutture Dati

Fractional knapsack (zaino frazionario)

Dato n oggetti con i rispettivi pesi e valori, si desidera inserire questi oggetti in uno zaino di capacità W in modo da ottenere il valore totale massimo possibile. È permesso prendere solo una frazione (parte) di un oggetto, e in tal caso il valore relativo viene ridimensionato proporzionalmente alla frazione scelta.

Qual è il massimo valore totale che si può raggiungere nello zaino?

Input

La prima riga dell’input contiene due interi n (1 ≤ n ≤ ), che indicano il numero di oggetti, e W (1 ≤ W ≤ ), la capacità dello zaino.

Le successive n righe contengono coppie di interi separate da uno spazio (1 ≤ , ≤ ), dove ciascuna coppia rappresenta il peso e il valore di un oggetto.

Output

Il programma deve stampare il valore totale massimo ottenibile nello zaino.

Esempi

Ingresso

Uscita

3 50
10 60
20 100
30 120

240

4 60
40 280
10 100
20 120
24 120

440

Spiegazione

  1. 60 + 100 + (2/3)120 = 240

  2. 280 + 100 + (10/20)120 = 440

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue