可消去的片段

一条记录由 $n$ 个符号组成，每个符号是 a、A、b、B 之一，并带有一个整数收益 $w_i$．其中 a 与 A 互相抵消，b 与 B 互相抵消．

一个非空连续片段如果能通过反复删除相邻且互相抵消的两个符号，最终删至空串，就称为“可消去片段”．例如 abBA 可以消空：先删中间的 bB，再删剩余的 aA．抵消与两个符号的顺序无关，Aa 和 Bb 也可以直接消去．

你可以选取任意多个两两不重叠的可消去片段，获得这些片段内所有位置的收益之和．每个片段均按原字符串中的连续位置选取；不同片段可以相邻，但不能共享位置．也可以一个片段都不选，此时收益为 $0$．求最大总收益．

输入格式

第一行输入一个整数 $n$．

第二行输入长度为 $n$ 的字符串 $s$．

第三行输入 $n$ 个整数 $w_1,w_2,\ldots,w_n$．

输出格式

输出一个整数，表示最大总收益．

样例 1

4
aAbB
3 2 4 -1

8

可以选取片段 $[1,2]$ 和 $[3,4]$，收益分别为 $5$ 和 $3$．

更多样例

点击下载本题选手目录

• Data/sample1.in 与 Data/sample1.ans：$n=2000$，满足子任务 1．
• Data/sample2.in 与 Data/sample2.ans：$n=200000$，满足子任务 2．
• Data/sample3.in 与 Data/sample3.ans：$n=200000$，满足子任务 3．
• Data/sample4.in 与 Data/sample4.ans：$n=200000$，该样例无特殊限制．
• Data/sample5.in 与 Data/sample5.ans：$n=8$，满足子任务 1．
• Data/sample6.in 与 Data/sample6.ans：题面中的样例．
• Data/sample7.in 与 Data/sample7.ans：$n=4$，满足子任务 1．
• Data/sample8.in 与 Data/sample8.ans：$n=6$，满足子任务 1．
• Data/sample9.in 与 Data/sample9.ans：$n=200000$，该样例无特殊限制．
• Data/sample10.in 与 Data/sample10.ans：$n=200000$，满足子任务 3．

下载样例与正式评测数据独立构造．通过下载样例不保证通过对应子任务．

数据范围与子任务

对于全部数据，$1\le n\le 2\times10^5$，$-10^9\le w_i\le10^9$，$s$ 只含 a、A、b、B．

一个字符串的“规范形”按以下方法得到：从左到右扫描字符串，维护一个初始为空的栈；若当前符号与栈顶符号互相抵消，就弹出栈顶，否则将当前符号压入栈．扫描结束后，栈内从底到顶的字符串就是其规范形．

各子任务独立计分．一个子任务内的全部测试点均通过，才能获得该子任务的分数．

子任务	分值	特殊性质
1	18	$n\le2000$
2		$s$ 只含 a 和 A
3	14	每个前缀的规范形长度均不超过 $20$
4	50	无特殊性质