L-贝贝的石子游戏_集美大学"第15届蓝桥杯大赛(软件类)"校内选拔赛

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

贝贝在玩一个石子游戏。 $n$ 个石子按从左往右的顺序排成一行，每个石子有一个重量和一个类型，类型分为 $A$ 和 $B$ 两种。其中第 $i$ 个石子的类型为 $s_i$ ，其重量为 $w_i$ 。

贝贝可以进行 $n$ 次操作，每次选择一个石子将其移走。
显然，最终所有石子都将被移走。

在这个过程中，你的得分如下：

对于一次操作，假设贝贝要移走第 $j$ 个石子（其中 $j$ 为该石子在初始石子序列中的编号）：

          1. 如果石子 $j$ 是还未移走的石子中最左侧或最右侧的石子，则得分为 $0$ 。
          2. 若与石子 $j$ 相邻的两个石子中（当前状态，不是初始状态），存在一个石子的类型与其相同，则得分为 $0$ 。
          3. 否则，得分为 $w_j$ 。

整个过程的得分为所有操作的得分之和。

贝贝的目标是最大化最终的得分。

但是众所周知贝贝是个菜狗，于是他向聪明的你寻求帮助，请你写一个程序告诉他得分的最大值为多少。

输入描述:

第一行，包含一个整数  。

第二行，包含一个长为  的字符串  ，每个字符只可能为  或  ，描述该石子的类型。

第三行，包含  个整数  ，描述每个石子的重量。

输出描述:

仅一行，包含一个整数，表示最大的得分。

示例1

输入

复制

3
ABA
1 2 3

输出

复制

示例2

输入

复制

7
AABBABA
2 4 5 1 3 7 6

输出

复制

备注:

对于至少  的数据有： 
对于至少  的数据有： 
对于至少  的数据有： 
对于至少  的数据有： 
对于至少  的数据有： 
对于  的数据有：  。