Problem description
Rozważamy plecak i zestaw N przedmiotów, które można umieścić w plecaku. Każdy przedmiot charakteryzuje się masą oraz wartością (pieniężną). Znając wszystkie dostępne przedmioty, interesujemy się wszystkimi podzbiorami tych przedmiotów, które mają łączną masę nieprzekraczającą W (więcej nie udźwigniemy niosąc plecak). Spośród takich podzbiorów wybieramy ten, w którym łączna wartość przedmiotów jest największa. Celem zadania jest wyznaczenie tej największej wartości.
Wejście
W pierwszej linijce wejścia znajduje się dokładnie jedna liczna naturalna N. W kolejnych N wierszach znajdują się opisy przedmiotów, po jednym na wiersz. Opis przedmiotu składa się z dwóch liczb naturalnych, przy czym pierwsza z nich określa masę danego przedmiotu, a druga – wartość. Ostatnia linijka zawiera jedną liczbę naturalną W, określającą maksymalny udźwig.
Wyjście
Na wyjściu należy podać jedną liczbę naturalną – największą możliwą sumaryczną wartość przedmiotów umieszczonych w plecaku dobranych tak, by ich łączna masa nie przekraczała W.
Ograniczenia
1 ≤ N ≤ 100, 0 ≤ W ≤ 1 000.
Przykład
| Input | Output | |
|
|