题目描述

一套信号网络由 $n$ 座中继站组成，编号为 $1\sim n$。第 $i$ 座中继站的收益为 $w_i\ (-10^9\leq w_i\leq 10^9)$，并且预先指定了另一座中继站 $a_i$ 作为它的信号参考源。

每座中继站保存一个二进制信号状态 $c_i$。初始时，只有中继站 $s$ 保存激活信号，即 $c_s=1$；其余中继站均未激活，即 $c_i=0\ (i\neq s)$。

你可以进行任意多次操作，也可以一次都不进行。每次操作选择一座中继站 $i$，支付 $p_i$ 的维护费用，使它立即同步参考站 $a_i$ 的当前信号状态，也就是令 $c_i\leftarrow c_{a_i}$。

网络调整结束后，所有满足 $c_i=1$ 的中继站都会贡献其收益 $w_i$。你的最终得分等于这些收益的总和减去全部操作费用。请合理安排操作，求能够获得的最大得分。

输入格式

第一行两个整数 $n,s$，表示中继站数量和初始信号状态为 $1$ 的中继站编号。

第二行 $n$ 个整数 $w_1,w_2,\cdots,w_n$，表示每座中继站的收益。

第三行 $n$ 个整数 $p_1,p_2,\cdots,p_n$，表示同步每座中继站所需的费用。

第四行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每座中继站对应的参考站编号。

输出格式

输出一行一个整数答案。

样例

样例1

样例输入

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

样例输出

1

样例解释

• 初始时，各中继站的信号状态为 $c=(1,0,0)$；
• 同步中继站 $2$，即执行 $c_2 \leftarrow c_{a_2}$，费用为 $p_2=0$，状态变为 $c=(1,1,0)$；
• 同步中继站 $1$，即执行 $c_1 \leftarrow c_{a_1}$，费用为 $p_1=1$，状态变为 $c=(0,1,0)$；
• 同步中继站 $3$，即执行 $c_3 \leftarrow c_{a_3}$，费用为 $p_3=0$，状态变为 $c=(0,1,1)$；
• 再次同步中继站 $2$，即执行 $c_2 \leftarrow c_{a_2}$，费用为 $p_2=0$，状态变为 $c=(0,0,1)$；
• 最终仅中继站 $3$ 处于激活状态，得分为 $w_3-(p_2+p_1+p_3+p_2)=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

样例输出

35343360

数据范围与提示

数据范围

本题采用子任务捆绑测试。

子任务 $1$ （ $8$ 分）： $n\leq 20$ ；
子任务 $2$ （ $16$ 分）： $a_i=\begin{cases}i-1&i>1\\n&i=1\end{cases}$ ；
子任务 $3$ （ $16$ 分）： $p_i=0$ ；
子任务 $4$ （ $28$ 分）： $w_i\geq 0$ ；
子任务 $5$ （ $32$ 分）： 无特殊限制。

所有数据满足： $1\leq s\leq n\leq 5000$ ， $-10^9\leq w_i\leq 10^9$ ， $0\leq p_i \leq 10^9$ ， $1\leq a_i\leq n$ 且 $a_i\neq i$ 。