该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

C

有 $n$ 个 石子 按从左往右的顺序排成一行，每个 石子 有一个重量和一个类型，类型分为 A 和 B 两种。其中第 $i$ 个 石子 的类型为 $s_i$，其重量为 $w_i$。你可以进行 $n$ 次操作，每次选择一个 石子 将其移走。显然，最终所有 石子 都将被移走。在这个过程中，你的得分如下：

• 对于一次操作，假设你移走了 石子 $j$：
  • 如果 石子 $j$ 是还未移走的 石子 中最左侧或最右侧的 石子 ，则得分为 $0$。
  • 若与 石子 $j$ 相邻的两个 石子 中，存在一个 石子 的类型与其相同，则得分为 $0$。
  • 否则，得分为 $w_j$。
• 整个过程的得分为所有操作的得分之和。

你的目标是最大化最终的得分。你想要知道该得分最大为多少。

输入格式

输入的第一行包含一个整数 $n$。

接下来一行，包含一个长为 $n$ 的字符串 $S=s_1s_2\cdots s_n$，每个字符只可能为 A 或 B，描述该 石子 的类型。

接下来一行，包含 $n$ 个整数 $w_1,w_2,\cdots, w_n$，描述每个 石子 的重量。

输出格式

输出一行一个整数，表示最大的得分。

样例数据

3
ABA
1 2 3

2

7
AABBABA
2 4 5 1 3 7 6

12

样例 3

见下发文件。

子任务

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le w_i \le 10^9$。