Даны $n$ элементов, пронумерованных от $1$ до $n$. Элемент $i$ имеет значение $w_i$ и цвет $c_i$. У каждого элемента также есть указатель $a_i$ на некоторый другой элемент.

Изначально цвет элемента $s$ равен $1$, а цвет всех остальных элементов равен $0$. Формально, $c_s = 1$ и $c_i = 0$ для всех $i \neq s$ ($1 \le i \le n$).

Вы можете выполнять следующую операцию любое количество раз: * Присвоить $c_i \leftarrow c_{a_i}$ с затратами $p_i$.

Ваш итоговый результат равен сумме значений всех элементов с цветом $1$ после выполнения операций минус сумма затрат на операции.

Найдите максимально возможный результат, который можно получить.

Входные данные

Первая строка содержит два целых числа $n, s$ ($1 \le s \le n \le 5 \times 10^3$) — количество элементов и индекс элемента, имеющего цвет $1$ изначально.

Вторая строка содержит $n$ целых чисел $w_1, w_2, \dots, w_n$ ($-10^9 \le w_i \le 10^9$) — значения элементов.

Третья строка содержит $n$ целых чисел $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^9$) — стоимость изменения цвета каждого элемента.

Четвертая строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n, a_i \neq i$).

Выходные данные

Выведите одно целое число, представляющее ответ.

Примеры

Входные данные 1

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

Выходные данные 1

1

Входные данные 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

Выходные данные 2

35343360

Примечание

(There won’t be extra line breakers in the actual test cases.)

Примечание

В первом примере можно последовательно выполнить следующие операции:

1. Присвоить $c_2 \leftarrow c_{a_2}$ с затратами $p_2$, тогда $c = [1, 1, 0]$;
2. Присвоить $c_1 \leftarrow c_{a_1}$ с затратами $p_1$, тогда $c = [0, 1, 0]$;
3. Присвоить $c_3 \leftarrow c_{a_3}$ с затратами $p_3$, тогда $c = [0, 1, 1]$;
4. Присвоить $c_2 \leftarrow c_{a_2}$ с затратами $p_2$, тогда $c = [0, 0, 1]$.

После операций только цвет элемента $3$ равен $1$, поэтому результат равен $w_3 - (p_2 + p_1 + p_3 + p_2) = 1$. Можно показать, что получить результат больше $1$ невозможно.