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

3
8 40
5 20
3 22
10

42