题目描述

Alice 和 Bob 正在玩一款游戏

初始，Alice 可以设定一个长度为 $n$ 字符串 $\tt AB$ 串（仅有 $\tt A$ 和 $\tt B$），Bob 可以选择某个前缀或后缀进行翻转（指原本的 $\tt A$ 变为 $\tt B$，$\tt B$ 变为 $\tt A$），当然也可以不选。

最后每个玩家所获得的力量：若字符串中第 $i$ 个位置为 $\tt A$，则给予 Alice $p_i$ 点能量；若为 $\tt B$，则给予 Bob $p_i$ 点能量。求 Bob 进行翻转操作后所能得到的最大能量。

输入格式

第一行一个整数 $n$，$n\le 5\cdot 10^5$。

第二行 $n$ 个整数 $p_i$，$1\le p_i\le 10^9$。

第三行一个长度为 $n$ 的 $\tt AB$ 串。

输出格式

输出一个整数表示答案。

5
1 2 3 4 5
ABABA

11

5
1 2 3 4 5
AAAAA

15

1
1
B

1