I. Imaginary Dance Moves
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

SnowballSH is standing on a linear dance machine with $$$n$$$ squares in a row. By the rules, SnowballSH must move either left or right exactly one square every move. Initially, his score is $$$0$$$. Each square has a bonus value, and his final score is the sum of the bonus values of all the squares he has stepped on. Some squares have a negative bonus value, which means SnowballSH gets a penalty for stepping on there!

SnowballSH is currently standing at the $$$k-$$$th square from the left. Unfortunately, SnowballSH prepared his dance moves $$$s$$$ last night but forgot some of them. Help SnowballSH figure out the maximum score he could get after $$$|s|$$$ moves, if each missing dance move is replaced by either left or right.

Note that the initial square does not count towards the final score. If SnowballSH attempts to move left at the leftmost square, he will step on that square again, gaining its bonus. Similarly, if he attempts to move right at the rightmost square, he will step on that square again, gaining its bonus.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 1000)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ $$$(2 \le n \le 1000)$$$ and $$$k$$$ $$$(1 \le k \le n)$$$ — the number of squares on the machine and the position of SnowballSH's initial position, respectively. The leftmost square has position $$$1$$$ and the rightmost square has position $$$n$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(-10^5 \le a_i \le 10^5)$$$ — the bonus value for each square.

The third line of each test case contains a string $$$s$$$ $$$(1 \le |s| \le 2000)$$$, the dance moves SnowballSH will perform. A missing dance move will be denoted as a ?, a left move will be denoted as L, and a right move will be denoted as R. These are the only three characters that could appear in $$$s$$$.

It is guaranteed that both the sum of $$$n$$$ and the sum of $$$|s|$$$ over all test cases are not greater than $$$2000$$$.

Output

For each test case, print a single integer — the maximum score SnowballSH could get by replacing each ? with an L or R.

Example
Input
4
5 3
3 5 8 2 3
LRLLLL
7 5
-7 0 3 15 1 -6 9
?RL??LRRR
4 1
1 -100 -200 800
????L
8 8
1 2 3 9 6 3 2 1
??L?RR????RR?
Output
27
62
1100
74
Note

For the first test case, SnowballSH didn't forget any dance move, so he starts at $$$8$$$ (position $$$3$$$) and goes to $$$5, 8, 5, 3, 3, 3$$$ in order. His score is $$$5 + 8 + 5 + 3 + 3 + 3 = 27$$$.

For the second test case, SnowballSH starts at $$$1$$$ (position $$$5$$$). He can complete the dance moves as LRLLRLRRR to achieve a maximum score of $$$15 + 1 + 15 + 3 + 15 + 3 + 15 + 1 - 6 = 62$$$.

The moves for test cases 3 and 4 are RRRRL and LLLLRRLLRLRRL, respectively.