长度为 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