Satisfaction

You have vacation for the next $N$ days. Each day you will either create a problem or you will hold a contest with exactly one problem. Formally speaking, your action for the next $N$ days can be described by a string of length $N$ containing characters ‘P’ and ‘C’. If the $i^{th}$ character is ‘P’ then you will be creating a problem on $i^{th}$ day, if $i^{th}$ character is ‘C’ then you will hold a contest on that day with a problem that is created before $i^{th}$ day and unused till then. Each problem has an interesting factor and each contest has an importance factor. If you put a problem with interesting factor $x$ to a contest of importance factor $y$, then you get $x \times y$ satisfaction.

You need to put problems to contests in such a way that the sum of your satisfaction is maximized. Also the interesting factor of the problems are non increasing as your are not getting any sharper day by day. Input will be generated in a way that, for each contest you will have at least one problem available and as you love contests, you will not miss the chance to be the problem-setter in any contest.

Input

First line contains number of test cases $T(1\le T\le 10000)$.

Each testcase starts with an integer $N(1\le N\le 10^6)$.

The next line contains a string $A(A[1]…A[N])$ containing $N$ characters, each character is either ‘P’ or ‘C’.

The next line contains $N$ space separated integers $V[1],V[2],….,V[N]$, if $A[i] = ‘P’$ then $V[i]$ denotes interesting factor of the problem that you create on $i^{th}$ day, else $V[i]$ denotes importance factor of the contest on $i^{th}$ day.

For all $1\le i\le N$, $1\le V[i]\le 10^6$

If $i \lt j$ and $A[i] = A[j] = ‘P’$ then $V[i] \ge V[j]$

It's guaranteed that the sum of $N$ over all test cases does not exceed $10^6$.

Output

For each case, output a single integer, which denotes the maximum satisfaction you can get if you optimally place the problems in the contests.

Sample

Input	Output
2 5 PPCPC 9 8 9 6 6 5 PPCPC 9 8 1 7 9	129 89

For the first testcase,
Answer is $9*9 + 6*8 = 129$. On the $1^{st}$ contest (day $3$) you will put the problem created on day $1$ and on the $2^{nd}$ contest (day $5$) you will assign the problem created on day $2$.

For the second testcase,
Answer is $8*1 + 9*9 = 89$. On the $1^{st}$ contest (day $3$) you will put the problem created on day $2$ and on the $2^{nd}$ contest (day $5$) you will assign the problem created on day $1$.