$n$개의 원소가 1부터 $n$까지 번호가 매겨져 있다. 원소 $i$는 값 $w_i$와 색상 $c_i$를 가진다. 또한 각 원소는 다른 어떤 원소를 가리키는 포인터 $a_i$를 가지고 있다.

초기에 원소 $s$의 색상은 1이고, 나머지 모든 원소의 색상은 0이다. 더 형식적으로 말하면, $c_s = 1$이고 모든 $i \neq s$ ($1 \le i \le n$)에 대해 $c_i = 0$이다.

당신은 다음 연산을 원하는 횟수만큼 수행할 수 있다: * $p_i$의 비용을 지불하고 $c_i \leftarrow c_{a_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

참고

첫 번째 예제에서, 다음과 같은 연산을 순차적으로 수행할 수 있다:

1. $p_2$의 비용으로 $c_2 \leftarrow c_{a_2}$를 수행하면, $c = [1, 1, 0]$이 된다.
2. $p_1$의 비용으로 $c_1 \leftarrow c_{a_1}$를 수행하면, $c = [0, 1, 0]$이 된다.
3. $p_3$의 비용으로 $c_3 \leftarrow c_{a_3}$를 수행하면, $c = [0, 1, 1]$이 된다.
4. $p_2$의 비용으로 $c_2 \leftarrow c_{a_2}$를 수행하면, $c = [0, 0, 1]$이 된다.

연산 후, 원소 3의 색상만 1이므로 점수는 $w_3 - (p_2 + p_1 + p_3 + p_2) = 1$이 된다. 1보다 큰 점수를 얻는 것은 불가능함이 증명될 수 있다.