14 ноября в США отмечается День семейной пижамы.
Фабрика «Сонный енот» готовит комплекты для праздничной фотосессии. Директор уверен: два человека в одинаковых пижамах — это один человек, который очень быстро бегает. Поэтому в каждом семейном комплекте обязательно должна быть одна красная и одна синяя пижама.
На конвейере в ряд лежат $$$n$$$ пижам, пронумерованных слева направо от $$$1$$$ до $$$n$$$. Цвет $$$i$$$-й пижамы задан символом $$$s_i$$$: R означает красный цвет, а B — синий. Ценность этой пижамы равна $$$a_i$$$.
За одну операцию сотрудник может снять с конвейера любые две соседние пижамы разных цветов и собрать из них комплект. Ценность комплекта равна сумме ценностей этих двух пижам. После снятия пары оставшиеся части ряда соединяются: пижамы, между которыми была снятая пара, становятся соседними.
Можно выполнить любое число операций, в том числе ни одной. Найдите максимально возможную суммарную ценность собранных комплектов.
В первой строке задано целое число $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — количество пижам на конвейере.
Во второй строке задана строка $$$s$$$ длины $$$n$$$, состоящая из символов R и B, — цвета пижам слева направо.
В третьей строке заданы $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — ценности пижам.
Выведите одно целое число — максимально возможную суммарную ценность собранных комплектов.
2RB5 9
14
7RRBBRRR100 1 3 4 1 100 1
108
4BBBB1 10 100 1000
0
В первом примере две пижамы образуют один комплект ценностью $$$5+9=14$$$.
Во втором примере можно сначала снять пижамы с исходными номерами $$$2$$$ и $$$3$$$, а затем — с исходными номерами $$$1$$$ и $$$4$$$. Суммарная ценность комплектов равна $$$(1+3)+(100+4)=108$$$. На конвейере останутся три красные пижамы.
В третьем примере все пижамы синие, поэтому собрать ни одного комплекта не получится.