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