Problem description

Rozważmy następującą wariację gry w bilarda (gry, w której kijem uderza się kule ustawione na stole, które mają wpaść do specjalnie wyznaczonych dziur w odpowiednich miejscach stołu). Na stole leży N kul bilardowych, ponumerowanych od 1 do N. Mamy w zasobach X energii. Wbicie kuli o numerze i kosztuje a_i energii. Nie można wbić danej kuli, jeżeli posiadana energia w danym momencie jest mniejsza od jej kosztu. Ponadto, dany jest ciąg p_i, dla i = 1, …, N. Jeżeli p_i =  − 1, to kula o numerze i może zostać wbita w dowolnym momencie. Jeżeli natomiast 1 ≤ p_i ≤ N, to kula o numerze i może zostać wbita dopiero po wbiciu kuli o numerze p_i.

Jaki jest największy numer kuli, jaką jesteśmy w stanie wbić, przy założeniu, że zawsze trafiamy?

Wejście

W pierwszym wierszu wejścia dane są dwie liczby naturalne N oraz X oznaczające liczbę kul oraz początkową energię. W następnym wierszu dany jest ciąg a₁, …, a_N, oznaczający energię potrzebną do wbicia kolejnych kul. W następnym wierszu dany jest ciąg p₁, …, p_N.

Wyjście

W jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą najwyższy numer kuli, jaki jesteśmy w stanie wbić, lub  − 1 jeżeli nie jest to możliwe.

Ograniczenia

1 ≤ N ≤ 200 000, 1 ≤ X ≤ 10¹⁵, 1 ≤ a_i ≤ 10⁹, 1 ≤ p_i ≤ N lub p_i =  − 1, ale p_i ≠ i, dla i = 1, …, N.

Podzadania

Przykład

6 7
1 2 4 3 10 100
-1 -1 -1 -1 -1 -1

4

5 12
1 2 3 5 8
-1 1 2 3 4

4

8 10
3 1 4 1 5 9 2 6
-1 1 2 -1 4 4 5 7

7

2 1000000000000000
1 1
2 1

-1