$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$ $w_1$ $w_2$ $\dots$ $w_n$ $p_1$ $p_2$ $\dots$ $p_n$ $a_1$ $a_2$ $\dots$ $a_n$

• $1 \le s \le n \le 5 \times 10^3$
• $-10^9 \le w_i \le 10^9$
• $0 \le p_i \le 10^9$
• $1 \le a_i \le n, a_i \neq i$

出力

得られるスコアの最大値を1行で出力せよ。

入出力例

入力 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$ となる。 これより大きいスコアを得ることは不可能であることが示せる。