CF2000D Right Left Wrong

Vlad发现了一个由 $n$ 细胞组成的条带，从左到右从 $1$ 到 $n$ 编号。在 $i$ 中，有一个正整数 $a_i$ 和一个字母 $s_i$ ，其中所有 $s_i$ 都是'L'或'R'。 Vlad邀请您尝试通过执行任意(可能为零)操作来获得最大可能的分数。 在一次操作中，您可以选择两个索引 $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$ 分; - 将 $s_i$ 替换为`.` - 对于所有 $l \le i \le r$ ，这意味着您不能再选择这些索引。 例如，考虑下面的strip: | $3$ | $5$ | $1$ | $4$ | $3$ | $2$ | --- | --- | --- | --- | --- | --- | | l | r | l | l | l | r | 您可以先选择 $l = 1$ ， $r = 2$ ，并将 $3 + 5 = 8$ 添加到您的分数中。 | $3$ | $5$ | $1$ | $4$ | $3$ | $2$ | --- | --- | --- | --- | --- | --- | |。|。| l | l | l | r | 然后选择 $l = 3$ ， $r = 6$ 并将 $1 + 4 + 3 + 2 = 10$ 添加到您的分数中。 | $3$ | $5$ | $1$ | $4$ | $3$ | $2$ | --- | --- | --- | --- | --- | --- | |。|。|。|。|。|。| 因此无法再进行其他操作，最终得分为 $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 \cdot 10^5$ 。

对于每个测试用例，输出一个整数—可以得分的最大可能点数。