题目描述

给出未来 $N$ 天的天气，用字符串 $S$ 表示。$S$ 的第 $i$ 个字符是 S 表示第 $i$ 天晴天，是 R 表示第 $i$ 天雨天。初始时你的愉悦度为 $0$。

你可以进行任意多次（也可以 $0$ 次）下面的操作：

• 选一个整数 $i$（$1 \le i \le N$）；
• 把第 $i$ 天的天气取反：晴天变雨天，雨天变晴天；
• 每修改一次第 $i$ 天，愉悦度减少 $X_i$（同一天被改多次就要扣多次，所以显然没必要改两次）。

所有操作结束后，按最终的天气结算奖励：

• 对每个整数 $i$（$1 \le i \le N-1$），如果最终第 $i$ 天是雨天且第 $i+1$ 天是晴天，愉悦度增加 $Y_i$。

请求出能达到的愉悦度最大值。

本题有 $T$ 组测试数据，请对每组分别求解。

输入格式

T
case_1
case_2
...
case_T

每组测试数据的格式为：

N
S
X_1 X_2 ... X_N
Y_1 Y_2 ... Y_{N-1}

输出格式

输出 $T$ 行，第 $i$ 行是第 $i$ 组测试数据的答案。

输入示例 1

5
6
SRRRSR
3 1 4 1 5 9
2 6 5 3 5
6
RSRSRS
10 10 10 10 10 10
1 1 1 1 1
2
RR
4 3
2
10
RSSRSSRSSR
75 49 79 37 16 9 38 49 69 54
23 100 73 63 66 23 51 65 67
20
SSSRSSSRRRRSSRSSRSSR
343191362 223147518 135066250 426658267 693515093 8023388 383375974 712283203 40447501 19870690 318452142 356265717 283999278 209219229 418603824 39363351 392058270 254796273 110117486 64951139
576697130 385986330 895027325 654885799 784214084 577658764 761714876 583039741 943991250 446493376 701505924 402891440 963636095 919408713 238125227 871191978 843843821 397910552 529447424

输出示例 1

5
3
0
165
5201284760

示例 1 说明

第 $1$ 组：一种最优方案是只改第 $3$ 天。

• 把第 $3$ 天由雨改晴，愉悦度减少 $X_3 = 4$，天气变成 晴、雨、晴、雨、晴、雨。
• 此时第 $2$ 天雨、第 $3$ 天晴，得 $Y_2 = 6$；第 $4$ 天雨、第 $5$ 天晴，得 $Y_4 = 3$。
• 总愉悦度 $-4 + 6 + 3 = 5$，这就是最大值。

第 $2$、$3$ 组：说明什么都不做有时才是最优的。第 $3$ 组中，若把第 $2$ 天改成晴天，花费 $X_2 = 3$ 却只赚 $Y_1 = 2$，反而亏损，所以答案是 $0$。

第 $5$ 组：答案为 $5201284760$，超过了 $32$ 位整数的范围，必须用 long long。

约束条件

• $1 \le T \le 10^4$
• $N$ 是 $2$ 以上 $2 \times 10^5$ 以下的整数
• $S$ 是长度为 $N$、由 S 和 R 组成的字符串
• $1 \le X_i \le 10^9$
• $1 \le Y_i \le 10^9$
• 单个输入文件中 $N$ 的总和不超过 $2 \times 10^5$