Se citesc un numar natural n, apoi n perechi (greutate, valoare) reprezentand n obiecte, si o capacitate maxima G. Determinati, folosind metoda Backtracking (fara programare dinamica), valoarea maxima totala ce poate fi obtinuta alegand un subset de obiecte a caror greutate totala nu depaseste G.
- Date de intrare
- Pe prima linie se citeste n. Urmeaza n linii, fiecare cu doua numere: greutatea si valoarea unui obiect. Pe ultima linie se citeste G.
- Date de iesire
- Se afiseaza un singur numar: valoarea maxima totala obtinuta.
- Restrictii
- 1 <= n <= 16, 1 <= greutate, valoare <= 1000, 1 <= G <= 10000
Exemple
Exemplul 1
Intrare
3 2 3 3 4 4 5 5
Iesire
7
Exemplul 2
Intrare
4 1 1 2 2 3 3 4 4 5
Iesire
5