问题 D: zz的游戏

内存限制：256 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：254 通过：77

返回比赛提交提交记录

zz 和 kk 正在玩一款游戏, 初始，zz 可以设定一个长度为 $n$ 字符串 AB 串（仅有 A 和 B），kk可以选择某个前缀或后缀进行一次翻转（指原本的 A 变为 B，B变为 A），当然也可以不选。最后每个玩家所获得的力量：

若字符串中第 $i$ 个位置为 A，则给予 zz P_i点能量；若为 B，则给予 kk $P i$ 点能量。求 kk 进行翻转操作后所能得到的最大能量。

第一行包含整数 n （1≤n≤5·10^5） −n个字符。
第二行包含 n 个整数 pi （1≤pi≤10^9） − 第 i 字符的能量。
第三行包含 n 个字符 A 或 B 。

打印唯一的整数 a − kk 可以达到的最大强度。

Examples

Input

5
1 2 3 4 5
ABABA

Output

Input

5
1 2 3 4 5
AAAAA

Output

Input

1
1
B

Output

Note
在第一个示例中，kk 应该翻转长度 1 的后缀。
在第二个示例中，kk 应该翻转长度为 5 的前缀或后缀（此处相同）。
在第三个示例中，kk 应该什么都不做。

5
1 2 3 4 5
ABABA

在第一个示例中，kk 应该翻转长度 1 的后缀。
在第二个示例中，kk 应该翻转长度为 5 的前缀或后缀（此处相同）。
在第三个示例中，kk 应该什么都不做。