F. Распалиндруй!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Строка a длины m называется антипалиндромной тогда и только тогда, когда m четное, и для каждого i (1 ≤ i ≤ m) ai ≠ am - i + 1.

У Ивана есть строка s из n строчных латинских букв; n четно. Он хочет построить некоторую строку t, которая будет антипалидромной перестановкой букв строки s. Также Иван определяет красоту индекса i как bi, а красоту строки t как сумму bi по всем таким индексам i, что si = ti.

Помогите Ивану определить максимальную красоту строки t, которую он может получить.

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

В первой строке записано одно целое число n (2 ≤ n ≤ 100, n четно) — количество букв в s.

Вторая строка содержит саму строку s. В ней присутствуют только строчные латинские буквы. Гарантируется, что можно переставить в ней буквы так, чтобы получить антипалиндромную строку.

Третья строка содержит n целых чисел b1, b2, ..., bn (1 ≤ bi ≤ 100), где bi — красота индекса i.

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

Выведите одно число — максимальную возможную красоту строки t.

Примеры
Входные данные
8
abacabac
1 1 1 1 1 1 1 1
Выходные данные
8
Входные данные
8
abaccaba
1 2 3 4 5 6 7 8
Выходные данные
26
Входные данные
8
abacabca
1 2 3 4 4 3 2 1
Выходные данные
17