题目描述

江月诗发现了一个由 $n$ 个单元格组成的长条，从左到右依次为 $1$ 到 $n$ 。在第 $i$ 个单元格中，有一个正整数 $a_i$ 和一个字母 $s_i$ ，其中所有的字母 $s_i$ 不是 "L"就是 "R"。

现在江月诗可以进行任意数量（可能为零）的操作，以获得尽可能高的分数。

在每一次操作中，江月诗可以选择两个索引 $l$ 和 $r$ ( $1 \le l < r \le n$ )，这样 $s_l$ = 'L'， $s_r$ = 'R'，然后进行以下操作：

• 将 $a_l + a_{l + 1} + \dots + a_{r - 1} + a_r$ 点的值加到他的分数上；
• 将所有 $l \le i \le r$ 的 $s_i$ 替换为'.'，这意味着江月诗不能再选择这些索引。

例如，请考虑以下条带：

你可以先选择 $l = 1$ ， $r = 2$ ，然后加上 $3 + 5 = 8$ 到你的得分 。

然后选择 $l = 3$ 、 $r = 6$ ，并将 $1 + 4 + 3 + 2 = 10$ 加入你的分数。

因此，不可能再进行其他操作，最终得分是 $18$ 。

请问江月诗能够得到最大得分是多少？

输入格式

第一行包含一个整数 $T$ ( $1 \le T \le 10^4$ ) 表示测试用例数。

每个测试用例的第一行包含一个整数 $n$ ( $2 \le n \le 2 \cdot 10^5$ ) 表示条带长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^5$ ) 表示写在条形图上的数字。

每个测试用例的第三行包含由 $n$ 个字符 "L "和 "R "组成的字符串 $s$ 。

保证所有测试用例中 $n$ 的值之和不超过 $2 \times 10^5$ 。

输出格式

对于每个测试用例，输出一个整数表示江月诗能够得到的最大分数。

输入样例

4
6
3 5 1 4 3 2
LRLLLR
2
2 8
LR
2
3 9
RL
5
1 2 3 4 5
LRLRR

输出样例

18
10
0
22