AT_arc211_c.[ARC211C] Forest

给定一个正整数 $N$，一个长度为 $N$ 的只由 # 和 . 组成的字符串 $S$，以及一个长度为 $N$ 的正整数序列 $R=(R_1,R_2,\dots,R_N)$。

有一个由 $N$ 个区域组成的森林，这些区域从左到右按 $1,2,\dots,N$ 排列。

有些区域长有树。具体地说，当且仅当 $S$ 的第 $i$ 个字符是 # 时，第 $i$ 区域有树。保证下述操作至少可以进行一次。

你可以重复进行如下操作任意次：

• 选取两个没有树的区域。设从左到右选中的区域编号为 $i$ 和 $j$（$i < j$）。那么区间 $i$ 到 $j$ 之间所有有树的区域的树都会被移除，并获得奖励 $R_i+R_j$。

注意，不能进行不会移除任何树的操作。

请你求出能使总奖励最大化的方案中，第一次操作可以有多少种选择方法。若两个选择方案中存在至少一个区域编号某一个被选中，另一个没被选中，则认为两种方案不同。

输入格式如下：

$N$ $S$ $R_1$ $R_2$ $\dots$ $R_N$

输出答案。

样例解释 1

共存在 6 种第一次操作方式如下：

• 选择区域 $1$ 和 $7$，移除区域 $4,5,6$ 的树，获得奖励 $21$。
• 选择区域 $1$ 和 $8$，移除区域 $4,5,6$ 的树，获得奖励 $21$。
• 选择区域 $2$ 和 $7$，移除区域 $4,5,6$ 的树，获得奖励 $26$。
• 选择区域 $2$ 和 $8$，移除区域 $4,5,6$ 的树，获得奖励 $26$。
• 选择区域 $3$ 和 $7$，移除区域 $4,5,6$ 的树，获得奖励 $2$。
• 选择区域 $3$ 和 $8$，移除区域 $4,5,6$ 的树，获得奖励 $2$。

无论选择哪一种操作，所有的树都会被移除，因此无法进行第二次操作。最大总奖励为 $26$。

样例解释 2

最大总奖励为 $825$。

注意目标不是最大化第一次操作获得的奖励。如果一开始选择区域 $1$ 和 $5$，可以获得 $422$ 的奖励，但之后不能再进行任何操作，因此总奖励不能达到 $825$。

约束条件

• $3\leq N\leq 2\times 10^5$
• $S$ 的长度为 $N$，且每个字符都是 # 或 .。
• $1\leq R_i\leq 10^9$，$1\leq i\leq N$
• 至少可以进行一次操作。
• $N$ 和 $R_i$ 都为整数。

由 ChatGPT 5 翻译