问题 G: 双相

本题改编自同名游戏

：对的对的对的！

：哦，不对不对不对！

：对……对吗？

题目描述

Mutsumi 和她的好朋友 Mortis 正在玩一个跑酷游戏，这个跑酷游戏的规则比较特殊：

游戏中有 $n+1$ 个格子，格子的编号从 0 到 $n$ ，每个格子的颜色是红色或者黑色，其中第 $i$ 个格子的分数为 aiai ，颜色为 sisi ，每个格子至多只能到达一次。

每次跳跃可以跳到一个没有到达过的格子上，跳跃完成后立刻切换玩家，Mutsumi 只能跳到红色的格子上，Mortis 只能跳到黑色的格子上。初始时 Mutsumi 在第 0 个格子开始跳跃，若某一个玩家无法进行跳跃，则游戏结束。

Mutsumi 和 Mortis 想知道，她们最终得分的最大值可能是多少？

第一行输入一个正整数 T（1≤T≤2×105）T（1≤T≤2×105） ，表示数据组数。

对于每一组数据：

第一行输入一个整数 n（1≤n≤2×105）n（1≤n≤2×105） ，表示格子数量。

第二行输入 $n$ 个整数 ai（1≤ai≤109）ai（1≤ai≤109） ，表示第 $i$ 个格子的得分。

第三行输入一个长度为 $n$ 仅包含 ′R′、′B′′R′、′B′ 两种字符的字符串 $s$ ， si=′R′,si=′B′si=′R′,si=′B′ 分别表示第 $i$ 个格子颜色为红色、黑色。

数据保证 ∑n≤2×106∑n≤2×106 。

Mutsumi 先从第 0 个格子跳到第 1 个格子，获得 1 分；

Mortis 从第 1 个格子跳到第 2 个格子，获得 1 分；

Mutsumi 从第 2 个格子跳到第 6 个格子，获得 4 分；

Mortis 从第 6 个格子跳到第 4 个格子，获得 5 分；

Mutsumi 从第 4 个格子跳到第 5 个格子，获得 1 分；

Mortis 从第 5 个格子跳到第 3 个格子，获得 4 分；

此时 Mutsumi 无法跳跃，游戏结束，总分为1+1+4+5+1+4=16。