Universities

You have just graduated from high school and are looking for a university to enroll in. Bytelandia has $N$ magic universities, and each one teaches either black magic or white magic. There are $N - 1$ bidirectional roads between the universities, and each road connects two different universities. The roads are laid out so that exactly one path exists between any two universities.

You plan to visit some of the universities. Each university has a happiness factor, and visiting it increases your overall happiness by that amount. If the happiness factor is negative, your overall happiness decreases instead.

To plan the trip you pick two different universities, the departure and the destination. You visit every university on the path between them, including both endpoints. To keep the trip balanced, you must visit the same number of white magic universities as black magic universities.

Find the largest possible sum of happiness factors over all trips that visit the same number of black magic and white magic universities.

The input consists of four lines.

The first line contains the number of universities $N$ ($2 \le N \le 10^5$). The universities are numbered from $1$ to $N$.

The second line contains a string of length $N$ made only of the characters "B" and "W". If the $i$-th character is "B", university $i$ teaches black magic, and if it is "W", university $i$ teaches white magic. At least one university teaches black magic and at least one teaches white magic.

The third line contains the happiness factors $h_1, h_2, \dots, h_N$ separated by spaces ($-10^5 \le h_i \le 10^5$).

The fourth line contains $N - 1$ integers $v_1, v_2, \dots, v_{N-1}$ separated by spaces. $v_i$ means a road connects university $v_i$ and university $i + 1$ ($1 \le v_i \le i$).

Print one integer, the maximum sum of happiness factors over all trips that visit the same number of black magic and white magic universities.