You, the wisest minion in town, is selecting a magic school for your brother Stuart to enrol in the coming year. There are N magic school in Fabulous-Imagination Town (FIT). Each school teaches either blue magic or white magic. There are N-1 bidirectional roads between the schools, each road connecting two different schools. Schools are connected in such a way, that there exists a unique path between any two schools.

You plan to visit some of the schools. Each school has a happiness factor, by which your overall happiness increases when you visit the school. Note that if the happiness factor is negative, your overall happiness decreases.

To plan your trip, you choose two different schools, the departure and destination school. You will visit all the schools on the path between the departure and the destination schools, both of them including. To keep things in balance, you must visit the same number of white magic schools as blue magic schools.

You are now wondering, what is the optimal trip that maximize the happiness of the trip, i.e. sum of the happiness factors of the schools you visit.

Given the description of schools and connections between them, Find the optimal trip around the schools, in which you visit the same number of blue and while magic schools and the happiness of the trip is as large as possible.

Input

Input consists of four lines.

First line contains a single integer N (2<=N<=10^5), number of schools (schools are numbered from 1 to N).

Second line contains a string of length N, consisting of "B" and "W" characters. If the i-th character is "B", then the i-th school is teaching blue magic. If the i-th character is "W", then the i-th school is teaching white magic. There will be at least one school teaching white magic ad at least one school teaching blue magic.

Third line contains N space-separated integers h_1, h_2 ... h_N (-10^5 <= h_i <= 10^5). Integer h_i is the happiness factor of the i-th school.

Fourth line contains N - 1 space-separated integers v_1, v_2 ... v_(N-1). Integer v_i means there is a road connecting the schools with numbers v_i and (i+1) (1<=v_i<=i).

Output

Output exactly one integer, maximum overall happiness of the trip, in which you visit the same number of blue and white magic schools.

Example

Input:
6
BWBBBW
6 0 3 -2 100 5
1 2 2 4 4

Output:
9