← 返回题目列表

Codeforces · 884/F

F. 反回文化

中文机器翻译题面 查看原题

长度为 m 的字符串 a 被称为反回文当且仅当 m 是偶数,并且对于每个 i (1 ≤ i ≤ m) ai ≠ am - i + 1。

Ivan 有一个由 n 个小写拉丁字母组成的字符串 s; n 是偶数。他想要形成一些字符串 t,它将成为 s 的反回文排列。 Ivan 还将索引 i 的美度表示为 bi,将 t 的美度表示为所有索引 i 中 bi 的总和,使得 si = ti。

帮助 Ivan 确定他可以获得的最大可能的美丽。

输入

第一行包含一个整数n(2≤n≤100,n为偶数)——s中的字符数。

第二行包含字符串 s 本身。它仅由小写拉丁字母组成,并且保证其字母可以重新排序以形成反回文字符串。

第三行包含n个整数b1, b2, ..., bn (1 ≤ bi ≤ 100),其中bi是索引i的美度。

输出

打印一个数字 — t 的最大可能之美。

示例

输入 #1

8
abacabac
1 1 1 1 1 1 1 1

输出 #1

8

输入 #2

8
abaccaba
1 2 3 4 5 6 7 8

输出 #2

26

输入 #3

8
abacabca
1 2 3 4 4 3 2 1

输出 #3

17