CF2087E Color the Arrows

有 $n$ 个箭头依次画在一条纸带上，编号从 $1$ 到 $n$。每个箭头要么指向左边，要么指向右边。最初，所有箭头都被涂成蓝色。 每次操作，你可以将一个蓝色箭头重新涂成红色。第一次操作时，你可以选择任意一个箭头。之后的每一次操作，你只能选择上一次操作所涂箭头所指方向上的箭头。如果上一次涂色的箭头是左箭头，那么这次必须选择编号比上一次小的箭头；如果上一次是右箭头，则必须选择编号比上一次大的箭头。注意，箭头不需要相邻。 每个箭头被涂成红色时都有一个整数奖励（可能为负、为零或为正）。 最终得分为所有被涂成红色的箭头的奖励之和。你可以进行任意次数的操作（包括零次），问最大得分是多少。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \times 10^5$），表示箭头的数量。 第二行是一个长度为 $n$ 的字符串，仅包含字符 ''，分别表示箭头指向左或右。 第三行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$-10^9 \le c_i \le 10^9$），表示每个箭头被涂成红色时的奖励。 输入的额外限制：所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$。

对于每个测试用例，输出一个整数，表示在允许进行任意次数操作（包括零次）的情况下，能够获得的最大得分。

在第一个测试用例中，你可以先将第 $2$ 个箭头涂成红色。这个箭头指向右边，所以下一步只能选择它右边的箭头。接着将第 $3$ 个箭头涂成红色。这个箭头也指向右边，因此不能再继续操作。答案为 $c_2 + c_3 = 4 + 6 = 10$。 在第二个测试用例中，你可以依次将第 $3$ 个和第 $1$ 个箭头涂成红色。 在第三个测试用例中，最优策略是不涂任何箭头，这样得分为 $0$，因为涂任何一个箭头都会导致总得分为负。 在第四个测试用例中，可以按顺序将第 $3, 7, 1, 5$ 个箭头涂成红色。 在第五个测试用例中，可以按顺序将第 $4, 3, 2, 1, 5$ 个箭头涂成红色。 由 ChatGPT 4.1 翻译