$N$ kamieni jest ułożonych w rzędzie. Każdy kamień jest koloru białego lub czarnego. Nazwijmy kamienie od lewej do prawej jako kamień 1, kamień 2, ..., kamień $N$. Waga $i$-tego kamienia wynosi $A_i$.

Będziesz wybierać i usuwać po jednym kamieniu z rzędu, powtarzając to $N$ razy, aż wszystkie kamienie zostaną usunięte.

Podczas usuwania kamienia, jeśli nie jest on obecnie ani skrajnie lewym, ani skrajnie prawym spośród pozostałych kamieni, a oba kamienie sąsiadujące z usuwanym kamieniem mają inny kolor niż on, Twój wynik wzrasta o wagę usuwanego kamienia. Dwa kamienie są sąsiednie, jeśli nie ma między nimi żadnych innych kamieni.

Znajdź sposób usuwania kamieni, który maksymalizuje Twój wynik.

Wejście

W pierwszym wierszu podana jest dodatnia liczba całkowita $N$ ($1 \le N \le 3 \times 10^5$).

W drugim wierszu podany jest ciąg znaków $S$ o długości $N$, składający się wyłącznie ze znaków B i W. $i$-ty znak ciągu $S$, oznaczony jako $S_i$, reprezentuje kolor $i$-tego kamienia od lewej. B oznacza, że kamień jest czarny, a W oznacza, że kamień jest biały.

W trzecim wierszu podanych jest $N$ liczb całkowitych $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$). $A_i$ reprezentuje wagę $i$-tego kamienia.

Wyjście

W pierwszym wierszu wypisz maksymalny wynik, jaki można uzyskać, usuwając kamienie w sposób optymalny.

Przykład

Wejście 1

4
WBWB
6 4 5 3

Wyjście 1

5

Wejście 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

Wyjście 2

13

Uwagi

Jeśli usuniemy kamienie w kolejności: 5., 6., 2., 3., 4., 7., 8. i 1. (odnosząc się do ich początkowych pozycji od lewej), otrzymamy punkty przy usuwaniu 3. oraz 5. kamienia, co da łącznie wynik 13.