AT_arc211_c [ARC211C] Forest

You are given a positive integer $ N $ , a string $ S $ of length $ N $ consisting of `#` and `.`, and a length- $ N $ sequence of positive integers $ R=(R_1,R_2,\dots,R_N) $ . There is a forest with $ N $ sections arranged in a single horizontal line. The sections are numbered $ 1,2,\dots,N $ from left to right. Some sections have trees. Specifically, section $ i $ has a tree if and only if the $ i $ -th character of $ S $ is `#`. It is guaranteed that the following operation can be performed at least once. You can repeat the following operation as many times as you like: - Choose two sections without trees. Let sections $ i $ and $ j $ (where $ i < j $ ) be the chosen sections from left to right. Then, all trees between sections $ i $ and $ j $ are removed, and you gain a reward of $ R_i+R_j $ . Here, you cannot perform an operation that removes no trees. Find the number of ways to perform the **first** operation to achieve the maximum possible total reward. Two ways are considered distinct if and only if there exists a section chosen in one way but not in the other.

The input is given from Standard Input in the following format: > $ N $ $ S $ $ R_1 $ $ R_2 $ $ \dots $ $ R_N $

Output the answer.

### Sample Explanation 1 There are six ways to perform the first operation, as follows: - Choose sections $ 1 $ and $ 7 $ . The trees at sections $ 4,5,6 $ are removed, and you gain a reward of $ 21 $ . - Choose sections $ 1 $ and $ 8 $ . The trees at sections $ 4,5,6 $ are removed, and you gain a reward of $ 21 $ . - Choose sections $ 2 $ and $ 7 $ . The trees at sections $ 4,5,6 $ are removed, and you gain a reward of $ 26 $ . - Choose sections $ 2 $ and $ 8 $ . The trees at sections $ 4,5,6 $ are removed, and you gain a reward of $ 26 $ . - Choose sections $ 3 $ and $ 7 $ . The trees at sections $ 4,5,6 $ are removed, and you gain a reward of $ 2 $ . - Choose sections $ 3 $ and $ 8 $ . The trees at sections $ 4,5,6 $ are removed, and you gain a reward of $ 2 $ . No matter which operation is performed, all trees are removed, so a second operation cannot be performed. The maximum possible total reward is $ 26 $ . ### Sample Explanation 2 The maximum possible total reward is $ 825 $ . Note that the goal is not to maximize the reward obtained in the first operation. If you choose sections $ 1 $ and $ 5 $ first, you can gain a reward of $ 422 $ , but no operation can be performed afterwards, and the total reward cannot reach $ 825 $ . ### Constraints - $ 3\leq N\leq 2\times 10^5 $ - The length of $ S $ is $ N $ , and each character is `#` or `.`. - $ 1\leq R_i\leq 10^9 $ $ (1\leq i\leq N) $ - The operation can be performed at least once. - $ N $ and $ R_i $ are integers.