Алиса и Боб играют в игру. Частью игры является разделение игровых фигур на две группы. Всего в игре есть n фигур и i-я из них имеет силу pi.
Фигуры разделяются на группы за несколько шагов:
Сила игрока определяется как суммарная сила фигур в группе игрока.
Вам задано начальное разделение Алисы на команды, помогите Бобу найти оптимальную стратегию. Выведите наибольшую силу, которую Боб может получить.
В первой строке находится целое число n (1 ≤ n ≤ 5·105) — количество игровых фигур.
Во второй строке находятся n целых чисел pi (1 ≤ pi ≤ 109) — сила i-й фигуры.
В третьей строке находятся n символов A или B — разделение на команды после первого хода (после хода Алисы).
Выведите одно целое число a — максимальную силу, которую Боб может получить.
В первом примере Боб должен поменять символы на суффиксе длины один.
Во втором примере Боб должен поменять символы на префиксе или суффиксе (здесь это одно и то же) длины 5.
В третьем примере Боб должен ничего не делать.
5 1 2 3 4 5 ABABA
11
5 1 2 3 4 5 AAAAA
15
1 1 B
1
1500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач