$N$ piedras etiquetadas del $1$ al $N$ están dispuestas en una fila en orden creciente. Cada piedra es de color blanco o negro. El peso de la $i$-ésima piedra es $A_i$.
Retirarás las piedras una a una hasta que todas hayan sido eliminadas.
Al retirar una piedra, si esta no es la que está más a la izquierda ni la que está más a la derecha de todas las piedras restantes, y ninguna de las dos piedras adyacentes a la piedra que se está retirando coincide con ella en color, tu puntuación aumenta en el peso de la piedra que se está retirando. Dos piedras son adyacentes si no hay otras piedras entre ellas.
Encuentra una forma de retirar las piedras para maximizar tu puntuación.
Entrada
La primera línea contiene un único entero $N$ ($1 \le N \le 300\,000$).
La segunda línea contiene una cadena $S$ de longitud $N$ donde cada carácter es B o W. El $i$-ésimo carácter de $S$, $S_i$, es B si la $i$-ésima piedra es negra, de lo contrario, $S_i$ es W y la $i$-ésima piedra es blanca.
La tercera línea contiene $N$ enteros $A_1, A_2, \cdots, A_N$ ($1 \le A_i \le 10^9$). $A_i$ representa el peso de la piedra $i$.
Salida
Imprime la puntuación máxima que se puede obtener si retiras las piedras de manera óptima.
Ejemplos
Entrada 1
4 WBWB 6 4 5 3
Salida 1
5
Entrada 2
8 WBBWBWBB 6 4 8 2 5 3 1 5
Salida 2
13
Nota
Si retiramos las piedras en el orden de sus posiciones iniciales 5, 6, 2, 3, 4, 7, 8, 1, obtenemos puntos al retirar la 3-ra y la 5-ta piedra, logrando un total de 13 puntos.