D. 左右错误（Right Left Wrong）
每个测试的时间限制：$2$ 秒
内存限制：$256$ 兆字节

Vlad 找到了一条有 $n$ 个格子的条带，格子从左到右编号为 $1$ 到 $n$。
在第 $i$ 个格子里，有一个正整数 $a_i$ 和一个字母 $s_i$，其中所有 $s_i$ 要么是 'L' 要么是 'R'。

Vlad 邀请你通过执行任意次（可能为零次）操作，来获得尽可能高的分数。

在一次操作中，你可以选择两个下标 $l$ 和 $r$（$1 \le l < r \le n$），满足 $s_l = \text{'L'}$ 且 $s_r = \text{'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$ 分。

状态变为：

无法再执行操作，最终得分为 $8 + 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$ 的字符串 $s$，只包含字符 'L' 和 'R'。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 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