$N$ pierres numérotées de $1$ à $N$ sont disposées en ligne dans l'ordre croissant. Chaque pierre est de couleur blanche ou noire. Le poids de la $i$-ème pierre est $A_i$.

Vous allez retirer les pierres une par une jusqu'à ce qu'elles soient toutes retirées.

Lorsque vous retirez une pierre, si cette pierre n'est ni la plus à gauche ni la plus à droite de toutes les pierres restantes, et qu'aucune des deux pierres adjacentes à la pierre retirée n'est de la même couleur qu'elle, votre score augmente du poids de la pierre retirée. Deux pierres sont adjacentes s'il n'y a pas d'autres pierres entre elles.

Trouvez une façon de retirer les pierres afin de maximiser votre score.

Entrée

La première ligne contient un unique entier $N$ ($1 \le N \le 300\,000$).

La deuxième ligne contient une chaîne de caractères $S$ de longueur $N$ où chaque caractère est soit B ou W. Le $i$-ème caractère de $S$, $S_i$, est B si la $i$-ème pierre est noire, sinon $S_i$ est W et la $i$-ème pierre est blanche.

La troisième ligne contient $N$ entiers $A_1, A_2, \cdots, A_N$ ($1 \le A_i \le 10^9$). $A_i$ représente le poids de la pierre $i$.

Sortie

Affichez le score maximum qui peut être obtenu si vous retirez les pierres de manière optimale.

Exemples

Entrée 1

4
WBWB
6 4 5 3

Sortie 1

5

Entrée 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

Sortie 2

13

Remarque

Pour le deuxième exemple, si l'on retire les pierres dans l'ordre suivant (par rapport à leurs positions initiales de gauche à droite) : la 5-ème, la 6-ème, la 2-ème, la 3-ème, la 4-ème, la 7-ème, la 8-ème, puis la 1-ère pierre, on obtient des points lors du retrait de la 3-ème et de la 5-ème pierre, ce qui donne un score total de 13 points.