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 翻译