← 返回题目列表

Codeforces · 2000/D

D. 右左错误

中文机器翻译题面 查看原题

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