Alice 和 Bob 正在玩游戏。游戏涉及将游戏棋子分成两队。有 n 块,第 i 块的强度为 pi。
分割游戏棋子的方式分为几个步骤:
1. 首先,Alice 将棋子分成两个不同的组 A 和 B。这可以看作是将棋子的团队分配写在 n 个字符的字符串中,其中每个字符是 A 或 B。
2. Bob 将选择字符串的任意前缀或后缀,并翻转该后缀中的每个字符(即,将 A 更改为 B,将 B 更改为 A)。这一步他最多可以做一次。
3. Alice 将获得所有标记为 A 的棋子,Bob 将获得所有标记为 B 的棋子。
玩家的力量就是该组中棋子的力量之和。
鉴于 Alice 最初分成两个团队,请帮助 Bob 确定最佳策略。返回他可以达到的最大力量。
输入
第一行包含整数 n (1 ≤ n ≤ 5·105) — 游戏棋子的数量。
第二行包含 n 个整数 pi (1 ≤ pi ≤ 109) — 第 i 块的强度。
第三行包含 n 个字符 A 或 B — 第一步之后(在 Alice 的步骤之后)的团队分配。
输出
打印唯一的整数 a — Bob 可以达到的最大强度。
示例
输入 #1
5 1 2 3 4 5 ABABA
输出 #1
11
输入 #2
5 1 2 3 4 5 AAAAA
输出 #2
15
输入 #3
1 1 B
输出 #3
1
注意
在第一个示例中,Bob 应该翻转长度为 1 的后缀。
在第二个示例中,Bob 应该翻转长度为 5 的前缀或后缀(此处相同)。
在第三个示例中,Bob 不应该执行任何操作。