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$$$,这意味着您无法再选择这些索引。
例如,考虑以下条带:
$$$3$$$$$$5$$$$$$1$$$$$$4$$$$$$3$$$$$$2$$$LRLLLR
您可以首先选择 $$$l = 1$$$、$$$r = 2$$$ 并将 $$$3 + 5 = 8$$$ 添加到您的分数中。
$$$3$$$$$$5$$$$$$1$$$$$$4$$$$$$3$$$$$$2$$$..LLLR
然后选择 $$$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$$$。
输出
对于每个测试用例,输出一个整数——可以得分的最大可能点数。
示例
输入 #1
4 6 3 5 1 4 3 2 LRLLLR 2 2 8 LR 2 3 9 RL 5 1 2 3 4 5 LRLRR
输出 #1
18 10 0 22