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$ 。

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