AT_arc211_c [ARC211C] Forest

正整数 $ N $ 、長さ $ N $ の `#` と `.` からなる文字列 $ S $ 、長さ $ N $ の正整数列 $ R=(R_1,R_2,\dots,R_N) $ が与えられます。 $ N $ 個の区画が横 $ 1 $ 列に並んだ森林があります。区画には左から順に $ 1,2,\dots,N $ と番号が付けられています。 いくつかの区画には木が生えています。具体的には、 $ S $ の $ i $ 文字目が `#` であるとき、またそのときに限り区画 $ i $ には木が生えています。ここで、次に示す操作を $ 1 $ 回以上行うことができることが保証されます。 あなたは、以下の操作を好きなだけ繰り返すことができます。 - 木が生えていない区画を $ 2 $ つ選ぶ。選んだ区画を左から区画 $ i,j $ とすると、区画 $ i $ と区画 $ j $ の間にある木がすべてなくなり、 $ R_i+R_j $ の報酬を得る。 ただし、木が $ 1 $ 本もなくならないような操作を行うことはできません。 最終的に獲得できる報酬の総和の最大値を達成するために、**最初に**行うことのできる操作の数を求めてください。ただし、 $ 2 $ つの操作は、どちらか一方のみで選んでいる区画が存在するとき、またそのときに限り区別します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $ $ R_1 $ $ R_2 $ $ \dots $ $ R_N $

答えを出力せよ。

### Sample Explanation 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 $ の報酬を得る。 どの操作を行ったとしてもすべての木がなくなるので、 $ 2 $ 回目の操作を行うことはできません。獲得できる報酬の総和の最大値は $ 26 $ です。 ### Sample Explanation 2 獲得できる報酬の総和の最大値は $ 825 $ です。 最初に得る報酬を最大化するのではないことに注意してください。最初に区画 $ 1 $ と区画 $ 5 $ を選ぶと $ 422 $ の報酬を獲得できますが、その後操作を行うことができず、報酬の総和を $ 825 $ にすることができません。 ### Constraints - $ 3\leq N\leq 2\times 10^5 $ - $ S $ の長さは $ N $ で、各文字は `#` または `.` - $ 1\leq R_i\leq 10^9 $ $ (1\leq i\leq N) $ - 操作を $ 1 $ 回以上行うことができる - $ N,R_i $ は整数