Plecak

Limit pamięci: 128 MB

Jaś i Małgosia wyjeżdżają na wycieczkę. Chłopiec, chcąc zaimponować koleżance, postanowił spakować ich rzeczy do jednego plecaka. Co więcej, im cięższy ten plecak będzie, tym lepsze zrobi wrażenie. Oczywiście Jaś nie może bez zastanowienia zapakować wszystkich rzeczy, które znajdzie w domu - przecież plecak mógłby się wtedy porwać (cóż to byłby za wstyd!).

Ponadto Jaś nie może dopuścić do sytuacji, w której np. zabrałby radio, ale zostawił baterie, albo wziął statyw, ale zapomniał aparatu. Dla każdego przedmiotu Jaś albo określił inny przedmiot , bez którego przedmiot byłby bezużyteczny, albo po prostu zaznaczył, że jest przedmiotem, który sam w sobie jest przydatny.

Pomóż naszemu bohaterowi i oblicz, jak ciężką zawartość plecaka może uzyskać, nie przekraczając jego maksymalnego udźwigu i nie zabierając żadnego bezużytecznego przedmiotu.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (, ), oznaczające liczbę przedmiotów, których zabranie rozważa Jaś, oraz udźwig plecaka w kilogramach - jeśli zapakujemy przedmioty o sumarycznej masie przekraczającej , plecak porwie się.

Zakładamy, że przedmioty są ponumerowane liczbami od 1 do . W kolejnych wierszach znajdują się opisy przedmiotów - opis przedmiotu o numerze składa się z dwóch liczb i (, ), oznaczających kolejno numer przedmiotu, który musi być w plecaku, aby można było zapakować tam przedmiot (jeśli , to przedmiot można zapakować bezwarunkowo), oraz masę przedmiotu w kilogramach.

Wyjście

Twój program powinien wypisać na wyjście jedną liczbę całkowitą: maksymalną masę zawartości plecaka (w kilogramach), jaką Jaś może uzyskać.

Przykład

Dla danych wejściowych:

7 11
0 3
0 1
2 3
2 2
4 4
5 3
5 2

poprawną odpowiedzią jest:

10

Autor zadania: Piotr Sankowski.