CF632B.Alice, Bob, Two Teams

Alice and Bob are playing a game. The game involves splitting up game pieces into two teams. There are n pieces, and the i-th piece has a strength p__i.

The way to split up game pieces is split into several steps:

1. First, Alice will split the pieces into two different groups A and B. This can be seen as writing the assignment of teams of a piece in an n character string, where each character is A or B.
2. Bob will then choose an arbitrary prefix or suffix of the string, and flip each character in that suffix (i.e. change A to B and B to A). He can do this step at most once.
3. Alice will get all the pieces marked A and Bob will get all the pieces marked B.

The strength of a player is then the sum of strengths of the pieces in the group.

Given Alice's initial split into two teams, help Bob determine an optimal strategy. Return the maximum strength he can achieve.

爱丽丝和鲍勃正在玩一个游戏。游戏涉及将游戏道具分成两支队伍。一共有 $n$ 个道具，其中第 $i$ 个道具的强度为 $p_i$。

分组过程分为以下几步：

1. 首先，爱丽丝将所有道具划分为两个不同的组 $A$ 和 $B$。这等价于构造一个长度为 $n$ 的字符串，字符串中每个字符为 $A$ 或 $B$，表示对应道具被分配到的队伍。
2. 接着，鲍勃任选该字符串的一个前缀或后缀，并将其中每个字符翻转（即把 $A$ 变为 $B$，$B$ 变为 $A$）。此操作至多执行一次。
3. 最终，所有标记为 $A$ 的道具归爱丽丝，所有标记为 $B$ 的道具归鲍勃。

每位玩家的强度等于其所属组中所有道具强度之和。

给定爱丽丝初始的分组方案，请帮助鲍勃确定最优策略，并返回他所能达到的最大强度。

The first line contains integer n (1 ≤ n ≤ 5·105) — the number of game pieces.

The second line contains n integers p__i (1 ≤ p__i ≤ 109) — the strength of the i-th piece.

The third line contains n characters A or B — the assignment of teams after the first step (after Alice's step).

第一行包含一个整数 $n$（$1 \leq n \leq 5\cdot10^5$）—— 游戏棋子的数量。

第二行包含 $n$ 个整数 $p_i$（$1 \leq p_i \leq 10^9$）—— 第 $i$ 个棋子的强度。

第三行包含 $n$ 个字符，每个字符为 A 或 B —— 第一步（即 Alice 的操作之后）的队伍分配情况。

Print the only integer a — the maximum strength Bob can achieve.

输出唯一的整数 $a$ —— Bob 能达到的最大力量值。

In the first sample Bob should flip the suffix of length one.

In the second sample Bob should flip the prefix or the suffix (here it is the same) of length 5.

In the third sample Bob should do nothing.

在第一个样例中，Bob 应翻转长度为 1 的后缀。

在第二个样例中，Bob 应翻转长度为 5 的前缀或后缀（此处两者相同）。

在第三个样例中，Bob 无需进行任何操作。