Vous disposez de $n$ éléments numérotés de $1$ à $n$. L'élément $i$ a une valeur $w_i$ et une couleur $c_i$. Chaque élément possède également un pointeur $a_i$ vers un autre élément.

Initialement, la couleur de l'élément $s$ est $1$, tandis que la couleur de tous les autres éléments est $0$. Plus formellement, $c_s = 1$ et $c_i = 0$ pour tout $i \neq s$ ($1 \le i \le n$).

Vous pouvez effectuer l'opération suivante autant de fois que vous le souhaitez :

• Assigner $c_i \leftarrow c_{a_i}$ pour un coût de $p_i$.

Votre score est égal à la somme des valeurs de tous les éléments de couleur $1$ après les opérations, moins la somme des coûts des opérations.

Trouvez le score maximum possible que vous pouvez obtenir.

Entrée

La première ligne contient deux entiers $n, s$ ($1 \le s \le n \le 5 \times 10^3$) — le nombre d'éléments et l'élément initialement de couleur $1$.

La deuxième ligne contient $n$ entiers $w_1, w_2, \dots, w_n$ ($-10^9 \le w_i \le 10^9$) — la valeur des éléments.

La troisième ligne contient $n$ entiers $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^9$) — le coût du changement de couleur de chaque élément.

La quatrième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n, a_i \neq i$).

Sortie

Affichez un seul entier représentant la réponse sur une ligne.

Exemples

Entrée 1

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

Sortie 1

1

Remarque

Dans le premier exemple, vous pouvez effectuer successivement les opérations suivantes :

1. Assigner $c_2 \leftarrow c_{a_2}$ pour un coût de $p_2$, alors $c = [1, 1, 0]$;
2. Assigner $c_1 \leftarrow c_{a_1}$ pour un coût de $p_1$, alors $c = [0, 1, 0]$;
3. Assigner $c_3 \leftarrow c_{a_3}$ pour un coût de $p_3$, alors $c = [0, 1, 1]$;
4. Assigner $c_2 \leftarrow c_{a_2}$ pour un coût de $p_2$, alors $c = [0, 0, 1]$.

Après les opérations, seul l'élément $3$ est de couleur $1$, donc votre score est égal à $w_3 - (p_2 + p_1 + p_3 + p_2) = 1$. Il peut être démontré qu'il est impossible d'obtenir un score supérieur à $1$.

Entrée 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

Sortie 2

35343360