AT_abc464_d [ABC464D] Celester

これから $ N $ 日間の天気が文字列 $ S $ として与えられます。 $ S $ の $ i $ 文字目が `S` であるとき $ i $ 日目の天気は晴れ、 `R` であるとき $ i $ 日目の天気は雨です。 また、現時点では嬉しさは $ 0 $ です。 あなたは、以下の操作を $ 0 $ 回以上何回でも行えます。 - $ 1 $ 以上 $ N $ 以下の整数 $ i $ を選ぶ。 - $ i $ 日目の天気が晴れであれば雨、雨であれば晴れに変更する。 - ただし、 $ i $ 日目の天気を変更した場合、嬉しさが $ X_i $ 減少する。 操作を行った後の最終的な天気に対して、以下の条件で嬉しさが増加します。 - $ 1 \le i \le N-1 $ を満たす各整数 $ i $ について、変更後の $ i $ 日目の天気が雨、かつ $ i+1 $ 日目の天気が晴れであるとき、嬉しさが $ Y_i $ 増加する。 操作を行った結果として、達成可能な嬉しさの最大値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。ここで $ \mathrm{case}_i $ は $ i $ 個目のテストケースを意味する。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ S $ $ X_1 $ $ X_2 $ $ \dots $ $ X_N $ $ Y_1 $ $ Y_2 $ $ \dots $ $ Y_{N-1} $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 個目のテストケースの答えを出力せよ。

### Sample Explanation 1 この入力には $ 5 $ 個のテストケースが含まれています。 $ 1 $ 個目のテストケースについて、例えば以下の通りに操作を行うことで嬉しさを最大とすることができます。 - $ 3 $ 日目の天気を雨から晴れに変更する。嬉しさが $ X_3=4 $ 減少し、各日の天気は 晴れ、雨、晴れ、雨、晴れ、雨 となります。 - この操作の結果、 $ 2 $ 日目が雨、 $ 3 $ 日目が晴れであることから嬉しさが $ Y_2=6 $ 増加し、 $ 4 $ 日目が雨、 $ 5 $ 日目が晴れであることから嬉しさが $ Y_4=3 $ 増加します。 - 全体の嬉しさは $ (-4)+6+3 = 5 $ であり、これが達成可能な最大です。 $ 2,3 $ 個目のテストケースについて、操作を行わないことが最適である場合があります。 $ 5 $ 個目のテストケースについて、答えが $ 32 $ bit 整数型に収まらない場合があることに注意してください。 ### Constraints - $ 1 \le T \le 10^4 $ - $ N $ は $ 2 $ 以上 $ 2 \times 10^5 $ 以下の整数 - $ S $ は長さ $ N $ の `S` と `R` からなる文字列 - $ X_i $ は $ 1 $ 以上 $ 10^9 $ 以下の整数 - $ Y_i $ は $ 1 $ 以上 $ 10^9 $ 以下の整数 - ひとつの入力における $ N $ の総和は $ 2 \times 10^5 $ 以下