解题思路

设灯珠状态串为 $s$，相邻权重为 $w_1,w_2,\dots,w_{n-1}$。

题目要求在至多一次翻转一个连续段 $[l,r]$ 后，使灯带的相融度最大。相融度定义为：

题目内容

有一条由 $n$ 个灯珠组成的灯带，每个灯珠仅有两种状态$0$ 或 $1$。灯带上相邻灯珠之间的焊点具有权重$w_i$（对应第$i$个灯珠与第$i+1$ 个灯珠之间的焊点）。定义灯带的相融度为所有相邻灯珠状态相同的焊点权重之和。

你可以进行至多一次翻转操作：选择一个连续段 $[l,r] (1≤l≤r≤n)$，将该段内的每个灯珠状态 $0$ 与 $1$互换$(0↔1)$。也可以不进行任何操作。请计算操作后灯带的相融度的最大值。

名词解释

• 相邻对：指灯珠 $i$ 与灯珠$i+1$组成的有序对$(1≤i≤n−1)$。
• 焊点权重：指相邻对$(i,i+1)$之间的权重 $w_i$，用于统计相融度。
• 相融度：所有满足灯珠$i$ 与$i+1$ 状态相同的相邻对的权重之和，即$\sum _{i=1}^{n−1}wi⋅[si=si+1]$其中$[⋅]$ 为指示函数（条件成立时为 $1$，否则为$0$）。
• 连续段：数组的一个闭区间子段$[l,r]$，包含位置$l,l+1,…,r$。
• 翻转操作：将选定连续段内每个灯珠状态 $0$ 与$1$ 互换。

输入描述

第一行输入整数$n (2≤n≤2×10^5)$，表示灯珠数量。

第二行输入一个长度为 n 的二进制字符串 $s$（字符仅为$'0'$或$'1'$），第 $i$个字符表示第$i$个灯珠的初始状态。

第三行输入$n−1$个整数 $w_1,w_2,…,w_{n−1} (1≤w_i≤10^9)$，表示各相邻对之间的焊点权重。

输出描述

输出一个整数，表示在进行至多一次翻转操作后，灯带的相融度最大值。

样例1

输入

5
01010
2 1 3 4

输出

7

说明

初始状态下任意相邻对状态均不同，相融度为$0$。若翻转连续段 $[4,4]$，灯带变为$01000$，相邻对$(3,4)$与 $(4,5)$ 状态相同，相融度为 $3+4=7$，这是最大值

样例2

输入

6
111000
1 2 3 4 5

输出

15

说明

初始相融度为$1+2+4+5=12$。若翻转连续段$[1,3]$，灯带变为$000000$，所有相邻对状态相同，相融度为$1+2+3+4+5=15$，为最大值。