Pointer Color Propagation

You are given n elements numbered from 1 to n. Each element i has a value \(w_i\) and a color \(c_i\), as well as a pointer \(a_i\) to some other element. Initially, the color of element s is 1 and the color of all other elements is 0, i.e. \(c_s=1\) and \(c_i=0\) for all \(i \neq s\) where \(1 \le i \le n\).

You can perform the following operation any number of times:

• For any element i, assign \(c_i \leftarrow c_{a_i}\) at a cost of \(p_i\).

After performing some operations, your score is the total of the values of all elements with color 1 minus the total cost spent on operations. Formally, if \(X\) is the set of elements whose color is 1 after the operations, your score is

[ \text{Score} = \sum_{i \in X} w_i - \sum_{\substack{i \in X\ i \neq s}} p_i. ]

Your task is to determine the maximum possible score.

Observation: An element i can only become 1 if its pointer \(a_i\) has already been set to 1. Hence, the set \(X\) of elements with color 1 (which you choose to update) must satisfy that if \(i \in X\) and \(i \neq s\) then \(a_i \in X\) as well. Equivalently, starting from s (which is already 1 and free), you can propagate the color to some elements by paying the corresponding cost \(p_i\) to gain the benefit \(w_i\).

The optimal strategy is to choose a subset \(X\) (with \(s\in X\)) such that the following holds:

[ \text{Score} = w_s + \sum_{\substack{i \in X\ i\neq s}} (w_i - p_i) ]

subject to: if \(i \in X\) and \(i \neq s\) then \(a_i \in X\).

This essentially forms a propagation tree (or forest) rooted at \(s\) when considering the pointers in reverse (i.e. for each \(i\), treat \(a_i\) as its parent). For every element i (except the initial element s), activating it yields a net gain of \(w_i - p_i\) (which could be negative). Furthermore, if an element has children that can yield a positive additional benefit, these can be added after activating the element. Therefore, if we define a function for any element \(i\) (other than \(s\)) as:

[ f(i) = w_i - p_i + \sum_{j \text{ is a child of } i} \max(0, f(j)), ]

then the maximum score achievable is given by:

[ \text{Answer} = w_s + \sum_{j \text{ is a child of } s} \max(0, f(j)). ]

</p>

Note that if an element is not reachable from s, it cannot be activated.

inputFormat

The input begins with a line containing two integers \(n\) and \(s\) (\(1 \le n \le 10^5\), \(1 \le s \le n\)), representing the number of elements and the starting element respectively.

The second line contains \(n\) integers \(w_1, w_2, \dots, w_n\) representing the values of the elements.

The third line contains \(n\) integers \(p_1, p_2, \dots, p_n\) representing the cost to perform the color copying operation on each element.

The fourth line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where \(a_i\) indicates the pointer of element i (\(1 \le a_i \le n\)).

outputFormat

Output a single integer representing the maximum achievable score.

sample

5 1
10 2 3 4 5
1 2 1 1 1
1 1 2 3 4

19