Prison Watch - Repovive Standard Round 4 | 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

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

11B. Prison Watch

Constraints

Input

Output

Samples

11B. Prison Watch

Constraints

Input

Output

Samples