题目内容

地铁站入口有 $n$ 台依次排列的闸机，每台只有两种状态，用字符 0 或 1 表示。相邻闸机 $i$ 与 $i+1$ 之间有协同权重 $w_i$，用于衡量两台闸机同时开或同时关时的通行效率。

运维把协同收益定义为所有状态相同的相邻对的权重之和，即 $\sum_{i=1}^{n-1} w_i \cdot [s_i=s_{i+1}]$，其中 $[\cdot]$ 在条件成立时为 1，否则为 0。

检修时至多做一次翻转：选择闭区间 $[l,r]$（$1 \le l \le r \le n$），把该区间内每台闸机的 0 与 1 互换；也可以不操作。

求操作后协同收益的最大值。

约束：闸机台数不超过 200000，权重为正整数且不超过 1000000000。

输入描述

第一行一个整数 $n$，表示闸机数量，满足 $2 \le n \le 200000$。 第二行一个长度为 $n$ 的字符串 $s$，仅含字符 0 与 1，第 $i$ 个字符为第 $i$ 台闸机的初始状态。 第三行 $n-1$ 个整数 $w_1,w_2,\ldots,w_{n-1}$，表示相邻闸机之间的权重，满足 $1 \le w_i \le 1000000000$。

输出描述

输出一个整数，表示至多一次翻转后协同收益的最大值。

样例1

输入

4
0011
5 8 3

输出

16

说明

初始状态 0011，同态相邻对贡献 $5+3=8$。 中间相邻对 0 与 1 不同，作为翻转边界可获得收益 8。 没有第二个正收益，答案为 $8+8=16$。

样例2

输入

3
101
7 2

输出

9

说明

状态 101 两个相邻对都不同，初始收益为 0。 把这两处都作为翻转边界，收益分别为 7 与 2，答案为 9。

样例3

输入

2
11
100

输出

100

说明

仅两个货架且状态相同，初始收益为 100。 翻转边界只会减少收益，因此不操作，答案仍为 100。

样例4

输入

7
0001110
3 9 1 4 6 2

输出

25

说明

先累加初始同态收益，再取相邻对翻转收益中最大的两个正数。 计算后答案为 25。