#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/11/problems/B

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Prison Watch - Repovive Standard Round 4 | Repovive | Repovive

11B. Prison Watch

1000 pts1s256 MB

There are $n$ prison cells in a row, numbered from $1$ to $n$ .

There is one guard in each cell. The direction of the guards is given by a string $s$ of length $n$ .

If $s_i = L$ , then guard $i$ sees every cell $j$ such that $1 \le j \le i$ .
If $s_i = R$ , then guard $i$ sees every cell $j$ such that $i \le j \le n$ .

In particular, every guard sees their own cell.

Hiring guard $i$ costs $a_i$ .

For each test case, find the minimum total cost needed to hire some guards so that every cell is seen by at least one hired guard.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$s_i \in \{L, R\}$
$1 \le a_i \le 1000$

Input

t

\left. \begin{array}{l} n \\ s \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

1
L
7

Case 2

4
RRRR
5 2 9 4

Case 3

5
LLLLL
6 1 8 3 4

Case 4

4
LLRR
10 3 2 9

Case 5

7
RLRLLRL
100 7 6 20 2 1 90

Explanation

Case 1

The only guard sees the only cell, so cost 7 is necessary.

Case 2

Only guard 1 can see cell 1 while facing right, and it also sees every cell. So the minimum cost is 5.

Case 3

Only guard 5 can see cell 5 while facing left, and it also sees every cell. So the minimum cost is 4.

Case 4

Hiring guard 2 and guard 3 covers cells 1, 2 and 3, 4 with total cost 5. No single guard sees all cells.

Case 5

Hiring guard 5 and guard 6 covers cells 1 through 5 and 6 through 7 with total cost 3, which is cheaper than either single guard that sees all cells.

Output

Case 1

Case 2

Case 3

Case 4

Case 5

There are $n$ prison cells in a row, numbered from $1$ to $n$ .

There is one guard in each cell. The direction of the guards is given by a string $s$ of length $n$ .

If $s_i = L$ , then guard $i$ sees every cell $j$ such that $1 \le j \le i$ .
If $s_i = R$ , then guard $i$ sees every cell $j$ such that $i \le j \le n$ .

In particular, every guard sees their own cell.

Hiring guard $i$ costs $a_i$ .

For each test case, find the minimum total cost needed to hire some guards so that every cell is seen by at least one hired guard.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$s_i \in \{L, R\}$
$1 \le a_i \le 1000$

t

\left. \begin{array}{l} n \\ s \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

11B. Prison Watch

Constraints

Input

Output

Samples

11B. Prison Watch

Constraints

Input

Output

Samples