B. Алиса, Боб, две команды
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. Частью игры является разделение игровых фигур на две группы. Всего в игре есть n фигур и i-я из них имеет силу pi.

Фигуры разделяются на группы за несколько шагов:

  1. Сначала Алиса разделяет фигуры на две группы A и B. Таким образом, Алиса записывает строку длины n, где i-й символ равен A или B в зависимости от группы i-й фигуры.
  2. Затем Боб выбирает некоторый суффикс или префикс, и меняет все символы на нём (то есть заменяет A на B, а B на A). Он это делает не больше одного раза.
  3. Алиса забирает все фигуры с буквой A, а Боб забирает фигуры с буквой B.

Сила игрока определяется как суммарная сила фигур в группе игрока.

Вам задано начальное разделение Алисы на команды, помогите Бобу найти оптимальную стратегию. Выведите наибольшую силу, которую Боб может получить.

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

В первой строке находится целое число n (1 ≤ n ≤ 5·105) — количество игровых фигур.

Во второй строке находятся n целых чисел pi (1 ≤ pi ≤ 109) — сила i-й фигуры.

В третьей строке находятся n символов A или B — разделение на команды после первого хода (после хода Алисы).

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

Выведите одно целое число a — максимальную силу, которую Боб может получить.

Примеры
Входные данные
5
1 2 3 4 5
ABABA
Выходные данные
11
Входные данные
5
1 2 3 4 5
AAAAA
Выходные данные
15
Входные данные
1
1
B
Выходные данные
1
Примечание

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

Во втором примере Боб должен поменять символы на префиксе или суффиксе (здесь это одно и то же) длины 5.

В третьем примере Боб должен ничего не делать.