Dany jest zbiór $n$ elementów ponumerowanych od $1$ do $n$. Element $i$ ma wartość $w_i$ oraz kolor $c_i$. Każdy element posiada również wskaźnik $a_i$ na pewien inny element.

Początkowo kolor elementu $s$ wynosi $1$, podczas gdy kolor wszystkich pozostałych elementów wynosi $0$. Formalnie, $c_s = 1$ oraz $c_i = 0$ dla wszystkich $i \neq s$ ($1 \le i \le n$).

Możesz dowolną liczbę razy wykonać następującą operację: * Przypisz $c_i \leftarrow c_{a_i}$ kosztem $p_i$.

Twój wynik jest równy sumie wartości wszystkich elementów o kolorze $1$ po wykonaniu operacji, pomniejszonej o sumę kosztów wykonanych operacji.

Znajdź maksymalny możliwy wynik, jaki możesz uzyskać.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite $n, s$ ($1 \le s \le n \le 5 \times 10^3$) — liczba elementów oraz element, który początkowo ma kolor $1$.

W drugiej linii znajduje się $n$ liczb całkowitych $w_1, w_2, \dots, w_n$ ($-10^9 \le w_i \le 10^9$) — wartości elementów.

W trzeciej linii znajduje się $n$ liczb całkowitych $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^9$) — koszt zmiany koloru każdego elementu.

W czwartej linii znajduje się $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n, a_i \neq i$).

Wyjście

Wypisz jedną liczbę całkowitą reprezentującą odpowiedź w jednej linii.

Przykład

Wejście 1

3 1
-1 -1 2
1 0 0
3 1 2

Wyjście 1

1

Wejście 2

10 8
36175808 53666444 14885614 -14507677
-92588511 52375931 -87106420 -7180697
-158326918 98234152
17550389 45695943 55459378 18577244
93218347 64719200 84319188 34410268
20911746 49221094
8 1 2 2 8 8 4 7 8 4

Wyjście 2

35343360

Uwagi

W pierwszym przykładzie można kolejno wykonać następujące operacje:

1. Przypisz $c_2 \leftarrow c_{a_2}$ kosztem $p_2$, wtedy $c = [1, 1, 0]$;
2. Przypisz $c_1 \leftarrow c_{a_1}$ kosztem $p_1$, wtedy $c = [0, 1, 0]$;
3. Przypisz $c_3 \leftarrow c_{a_3}$ kosztem $p_3$, wtedy $c = [0, 1, 1]$;
4. Przypisz $c_2 \leftarrow c_{a_2}$ kosztem $p_2$, wtedy $c = [0, 0, 1]$.

Po wykonaniu operacji tylko kolor elementu $3$ wynosi $1$, więc wynik jest równy $w_3 - (p_2 + p_1 + p_3 + p_2) = 1$. Można wykazać, że nie da się uzyskać wyniku większego niż $1$.