← 返回题目列表

Codeforces · 632/B

B. 爱丽丝,鲍勃,两队

中文机器翻译题面 查看原题

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 不应该执行任何操作。