题目描述

给定 $n$ 个元素，编号从 $1$ 到 $n$。元素 $i$ 的值为 $w_i$，颜色为 $c_i$。每个元素还有一个指针 $a_i$ 指向另一个元素。

最初，元素 $s$ 的颜色为 $1$，而所有其他元素的颜色都为 $0$。更正式地说，对于所有 $i\neq s$ $(1 \le i \le n)$，有 $c_s=1$ 和 $c_i=0$。

你可以任意多次执行以下操作：

• 以代价 $p_i$ 将 $c_i\leftarrow c_{a_i}$。

你的得分等于所有颜色为 $1$ 的元素值的总和减去操作的总代价。

找出你能够获得的最大可能得分。

输入格式

第一行包含两个整数 $n$ 和 $s$（$1 \leq s\le n \leq 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$）。

输出格式

输出一行一个整数，表示答案。

【样例解释】

在第一个样例中，你可以依次执行以下操作：

• 以代价 $p_2$ 将 $c_2\leftarrow c_{a_2}$，然后 $c=[1,1,0]$；
• 以代价 $p_1$ 将 $c_1\leftarrow c_{a_1}$，然后 $c=[0,1,0]$；
• 以代价 $p_3$ 将 $c_3\leftarrow c_{a_3}$，然后 $c=[0,1,1]$；
• 以代价 $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$ 的得分。

翻译来自于：ChatGPT

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

1

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

35343360