D - Celester 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

これから 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 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 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 以下

入力

入力は以下の形式で標準入力から与えられる。ここで \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 個目のテストケースの答えを出力せよ。

入力例 1

5
6
SRRRSR
3 1 4 1 5 9
2 6 5 3 5
6
RSRSRS
10 10 10 10 10 10
1 1 1 1 1
2
RR
4 3
2
10
RSSRSSRSSR
75 49 79 37 16 9 38 49 69 54
23 100 73 63 66 23 51 65 67
20
SSSRSSSRRRRSSRSSRSSR
343191362 223147518 135066250 426658267 693515093 8023388 383375974 712283203 40447501 19870690 318452142 356265717 283999278 209219229 418603824 39363351 392058270 254796273 110117486 64951139
576697130 385986330 895027325 654885799 784214084 577658764 761714876 583039741 943991250 446493376 701505924 402891440 963636095 919408713 238125227 871191978 843843821 397910552 529447424

出力例 1

5
3
0
165
5201284760

この入力には 5 個のテストケースが含まれています。

1 個目のテストケースについて、例えば以下の通りに操作を行うことで嬉しさを最大とすることができます。

  • 3 日目の天気を雨から晴れに変更する。嬉しさが X_3=4 減少し、各日の天気は 晴れ、雨、晴れ、雨、晴れ、雨 となります。
  • この操作の結果、 2 日目が雨、 3 日目が晴れであることから嬉しさが Y_2=6 増加し、 4 日目が雨、 5 日目が晴れであることから嬉しさが Y_4=3 増加します。
  • 全体の嬉しさは (-4)+6+3 = 5 であり、これが達成可能な最大です。

2,3 個目のテストケースについて、操作を行わないことが最適である場合があります。

5 個目のテストケースについて、答えが 32bit 整数型に収まらない場合があることに注意してください。

Score : 400 points

Problem Statement

The weather for the upcoming N days is given as a string S.
If the i-th character of S is S, then the weather on day i is sunny; if it is R, then the weather on day i is rainy.
Also, your current happiness is 0.

You can perform the following operation any number of times, possibly zero:

  • Choose an integer i with 1 \le i \le N.
  • If the weather on day i is sunny, change it to rainy; if it is rainy, change it to sunny.
  • However, if you change the weather on day i, your happiness decreases by X_i.

After performing the operations, your happiness increases based on the final weather according to the following condition:

  • For each integer i with 1 \le i \le N-1, if the weather on day i after modification is rainy and the weather on day i+1 is sunny, your happiness increases by Y_i.

Find the maximum value of happiness achievable by performing operations.

T test cases are given; solve each.

Constraints

  • 1 \le T \le 10^4
  • N is an integer between 2 and 2 \times 10^5, inclusive.
  • S is a string of length N consisting of S and R.
  • X_i is an integer between 1 and 10^9, inclusive.
  • Y_i is an integer between 1 and 10^9, inclusive.
  • The sum of N in a single input is at most 2 \times 10^5.

Input

The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
S
X_1 X_2 \dots X_N
Y_1 Y_2 \dots Y_{N-1}

Output

Output T lines. The i-th line should contain the answer for the i-th test case.

Sample Input 1

5
6
SRRRSR
3 1 4 1 5 9
2 6 5 3 5
6
RSRSRS
10 10 10 10 10 10
1 1 1 1 1
2
RR
4 3
2
10
RSSRSSRSSR
75 49 79 37 16 9 38 49 69 54
23 100 73 63 66 23 51 65 67
20
SSSRSSSRRRRSSRSSRSSR
343191362 223147518 135066250 426658267 693515093 8023388 383375974 712283203 40447501 19870690 318452142 356265717 283999278 209219229 418603824 39363351 392058270 254796273 110117486 64951139
576697130 385986330 895027325 654885799 784214084 577658764 761714876 583039741 943991250 446493376 701505924 402891440 963636095 919408713 238125227 871191978 843843821 397910552 529447424

Sample Output 1

5
3
0
165
5201284760

This input contains five test cases.

For the first test case, for example, you can maximize happiness by performing the following operations:

  • Change the weather on day 3 from rainy to sunny. Happiness decreases by X_3 = 4, and the weather on each day becomes sunny, rainy, sunny, rainy, sunny, rainy.
  • As a result of this operation, since day 2 is rainy and day 3 is sunny, happiness increases by Y_2 = 6, and since day 4 is rainy and day 5 is sunny, happiness increases by Y_4 = 3.
  • The total happiness is (-4) + 6 + 3 = 5, which is the achievable maximum.

For the second and third test cases, performing no operations may be optimal.

For the fifth test case, note that the answer may not fit in a 32-bit integer type.