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 $ i $ Jaś albo określił inny przedmiot $ j $, bez którego przedmiot $ i $ byłby bezużyteczny, albo po prostu zaznaczył, że $ i $ 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.

Input Format

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $ n $ i $ p $ ($1 \le n \le 200$, $1 \le p \le 10^{6}$), 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 $ p $, plecak porwie się.

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

Output Format

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

Example

Input

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

Output

10