Se te dan $n$ elementos numerados del 1 al $n$. El elemento $i$ tiene un valor $w_i$ y un color $c_i$. Cada elemento también tiene un puntero $a_i$ hacia algún otro elemento.

Inicialmente, el color del elemento $s$ es 1, mientras que el color de todos los demás elementos es 0. Más formalmente, $c_s = 1$ y $c_i = 0$ para todo $i \neq s$ ($1 \le i \le n$).

Puedes realizar la siguiente operación cualquier número de veces:

• Asignar $c_i \leftarrow c_{a_i}$ con un costo de $p_i$.

Tu puntuación es igual a la suma de los valores de todos los elementos con color 1 después de las operaciones, menos la suma de los costos de las operaciones.

Encuentra la máxima puntuación posible que puedes obtener.

Entrada

La primera línea contiene dos enteros $n, s$ ($1 \le s \le n \le 5 \times 10^3$) — el número de elementos y el elemento con color 1 inicialmente.

La segunda línea contiene $n$ enteros $w_1, w_2, \dots, w_n$ ($-10^9 \le w_i \le 10^9$) — el valor de los elementos.

La tercera línea contiene $n$ enteros $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^9$) — el costo de cambiar el color de cada elemento.

La cuarta línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n, a_i \neq i$).

Salida

Imprime un solo entero que represente la respuesta en una línea.

Ejemplos

Entrada 1

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

Salida 1

1

Nota

En el primer ejemplo, puedes realizar sucesivamente las siguientes operaciones:

1. Asignar $c_2 \leftarrow c_{a_2}$ con un costo de $p_2$, entonces $c = [1, 1, 0]$;
2. Asignar $c_1 \leftarrow c_{a_1}$ con un costo de $p_1$, entonces $c = [0, 1, 0]$;
3. Asignar $c_3 \leftarrow c_{a_3}$ con un costo de $p_3$, entonces $c = [0, 1, 1]$;
4. Asignar $c_2 \leftarrow c_{a_2}$ con un costo de $p_2$, entonces $c = [0, 0, 1]$.

Después de las operaciones, solo el color del elemento 3 es 1, por lo que tu puntuación es igual a $w_3 - (p_2 + p_1 + p_3 + p_2) = 1$. Se puede demostrar que es imposible obtener una puntuación mayor a 1.

Entrada 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

Salida 2

35343360