Bạn được cho $n$ phần tử được đánh số từ $1$ đến $n$. Phần tử $i$ có giá trị $w_i$ và màu $c_i$. Mỗi phần tử cũng có một con trỏ $a_i$ trỏ đến một phần tử khác.
Ban đầu, màu của phần tử $s$ là $1$, trong khi màu của tất cả các phần tử khác là $0$. Cụ thể hơn, $c_s = 1$ và $c_i = 0$ với mọi $i \neq s$ ($1 \le i \le n$).
Bạn có thể thực hiện thao tác sau bất kỳ số lần nào: * Gán $c_i \leftarrow c_{a_i}$ với chi phí $p_i$.
Điểm số của bạn bằng tổng giá trị của tất cả các phần tử có màu $1$ sau các thao tác trừ đi tổng chi phí của các thao tác.
Hãy tìm điểm số tối đa có thể đạt được.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên $n, s$ ($1 \le s \le n \le 5 \times 10^3$) — số lượng phần tử và phần tử có màu $1$ ban đầu.
Dòng thứ hai chứa $n$ số nguyên $w_1, w_2, \dots, w_n$ ($-10^9 \le w_i \le 10^9$) — giá trị của các phần tử.
Dòng thứ ba chứa $n$ số nguyên $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^9$) — chi phí để thay đổi màu của mỗi phần tử.
Dòng thứ tư chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n, a_i \neq i$).
Dữ liệu ra
In ra một số nguyên duy nhất đại diện cho kết quả trên một dòng.
Ví dụ
Dữ liệu vào 1
3 1 -1 -1 2 1 0 0 3 1 2
Dữ liệu ra 1
1
Ghi chú
Trong ví dụ đầu tiên, bạn có thể thực hiện liên tiếp các thao tác sau:
- Gán $c_2 \leftarrow c_{a_2}$ với chi phí $p_2$, khi đó $c = [1, 1, 0]$;
- Gán $c_1 \leftarrow c_{a_1}$ với chi phí $p_1$, khi đó $c = [0, 1, 0]$;
- Gán $c_3 \leftarrow c_{a_3}$ với chi phí $p_3$, khi đó $c = [0, 1, 1]$;
- Gán $c_2 \leftarrow c_{a_2}$ với chi phí $p_2$, khi đó $c = [0, 0, 1]$.
Sau các thao tác, chỉ có phần tử $3$ có màu $1$, vì vậy điểm số của bạn bằng $w_3 - (p_2 + p_1 + p_3 + p_2) = 1$. Có thể chứng minh rằng không thể đạt được điểm số lớn hơn $1$.
Dữ liệu vào 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
Dữ liệu ra 2
35343360
Ghi chú
(There won’t be extra line breakers in the actual test cases.)