$N$ 個の石が $1$ から $N$ までの番号が付けられ、一列に並んでいます。各石は白色または黒色に塗られています。$i$ 番目の石の重さは $A_i$ です。

あなたは、すべての石が取り除かれるまで、石を1つずつ取り除いていきます。

石を取り除くとき、その石が現在残っている石の中で最も左端でも右端でもなく、かつ取り除く石に隣接する2つの石の色がどちらも取り除く石の色と異なる場合、あなたの得点は取り除く石の重さだけ増加します。2つの石の間に他の石が存在しないとき、それらの石は隣接しているとみなします。

得られる得点を最大化するように石を取り除く方法を求めてください。

入力

最初の行に、正の整数 $N$ ($1 \le N \le 300\,000$) が与えられる。

2行目に、B または W からなる長さ $N$ の文字列 $S$ が与えられる。$S$ の $i$ 番目の文字 $S_i$ は、左から $i$ 番目の石の色を表す。B は黒色、W は白色を意味する。

3行目に、$N$ 個の整数 $A_1, A_2, \cdots, A_N$ ($1 \le A_i \le 10^9$) が与えられる。$A_i$ は $i$ 番目の石の重さを表す。

出力

最適な方法で石を取り除いたときに得られる最大得点を出力せよ。

入出力例

入力 1

4
WBWB
6 4 5 3

出力 1

5

入力 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

出力 2

13

注記

初期状態における左から $5, 6, 2, 3, 4, 7, 8, 1$ 番目の石をこの順に取り除くと、$3$ 番目の石と $5$ 番目の石を取り除くときに得点が得られ、合計 $13$ 点になります。