Se citesc n obiecte, fiecare cu o greutate si o valoare, si capacitatea G a unui rucsac. Din fiecare obiect se poate lua orice fractiune (nu neaparat intreg obiectul). Determinati, folosind metoda Greedy, valoarea maxima ce poate fi transportata fara a depasi capacitatea G.
- Date de intrare
- Pe prima linie se citesc n si G. Urmeaza n linii, fiecare cu doua numere: greutatea si valoarea unui obiect.
- Date de iesire
- Se afiseaza valoarea maxima, sub forma unei fractii ireductibile 'numarator/numitor' (sau doar 'numarator' daca valoarea este intreaga).
- Restrictii
- 1 <= n <= 1000, 0 <= G <= 10^6, 1 <= greutate, valoare <= 10^6
Exemple
Exemplul 1
Intrare
3 50 10 60 20 100 30 120
Iesire
240
Exemplul 2
Intrare
2 10 5 10 5 10
Iesire
20