Maximize your Balance#11860
Lisa is enjoying her summer vacation, which lasts for days. To make good use of her free time, she starts a small buy-and-sell business from her garage. Each day, she either buys a product from someone or sells something she no longer needs.
She keeps a record of her actions over the days in a notebook. For each day, she writes either '' if she bought a product or '' if she sold one. This gives her a string of length , where each character tells what she did on that day. She also keeps a list of the prices involved in the transactions. The price on i_{th} day is recorded at i_{th} position in an array. So the action and the price for each day go together.
Lisa wants to calculate her total balance. For every product she sold, she earns money equal to its price. For every product she bought, she spends money equal to its price. So, her balance is the total money earned from selling minus the total money spent on buying.
However, Lisa suspects that she might have accidentally mixed up the prices on some days. To fix this, she is allowed to swap the prices of any two different days, up to times. That means she can perform at most swaps of prices between any two days. She doesn't have to use all the swaps — using 1 or 0 is allowed if that gives a better result.
Can you help Lisa find the maximum balance she can get after doing at most single swap of prices?
The first line contains a single integer (1 \leq t \leq 10^4) — the number of test cases.
Each test case consists of three lines.
The first line contains single integer (1 \leq n \leq 2 \times 10^5) — the number of days.
The second line contains a string of length , consisting only of the characters and .
The third line contains integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9) — the price of the product on each day.
It is guaranteed that the sum of over all test cases does not exceed 2 \times 10^5.
Print a single integer — the maximum balance you can achieve after doing at most one swap of prices.
Please note ! that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).
Example 1
In the first test case , we can swap i=2 and i=3 then we've a=[1,3,2] and thus we've a total balance of -1+3-2=0.
In the second test case , we can swap i=3 and i=4 then we've a=[1,10,6,2] and thus we've a total balance of -1+10+6-2=13.
In the third test case , we cannot do any useful swaps since all of operations are buying operations , you've -(1+2+3+4+5)=-15.
In the fourth test case , we cannot do any useful swaps since all of operations are selling operations (1+1+1+1)=4.
Subtask ( points) : (s_i=\mathtt{B})
Subtask ( points) : (s_i=\mathtt{S})
Subtask ( points) : (1 \le \sum n \le 8)
Subtask ( points) : (1 \le \sum n \le 500)
Subtask ( points): No additional constraints.