$N$ камней, пронумерованных от $1$ до $N$, расположены в ряд в порядке возрастания. Каждый камень окрашен либо в белый, либо в черный цвет. Вес $i$-го камня равен $A_i$.

Вы будете поочередно удалять камни по одному, пока все камни не будут удалены.

При удалении камня, если он не является самым левым или самым правым среди всех оставшихся на данный момент камней, и ни один из двух соседних с ним камней не совпадает с ним по цвету, ваше количество очков увеличивается на вес удаляемого камня. Два камня считаются соседними, если между ними нет других оставшихся камней.

Найдите способ удаления камней, который максимизирует ваше итоговое количество очков.

Входные данные

В первой строке задано одно целое число $N$ ($1 \le N \le 300\,000$).

Во второй строке задана строка $S$ длины $N$, состоящая из символов B и W. $i$-й символ строки $S$, обозначаемый $S_i$, равен B, если $i$-й камень черный, и W, если $i$-й камень белый.

В третьей строке заданы $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 очков.