{"raw_statement":[{"iden":"statement","content":"A string _a_ of length _m_ is called _antipalindromic_ iff _m_ is even, and for each _i_ (1 ≤ _i_ ≤ _m_) _a__i_ ≠ _a__m_ - _i_ + 1.\n\nIvan has a string _s_ consisting of _n_ lowercase Latin letters; _n_ is even. He wants to form some string _t_ that will be an _antipalindromic_ permutation of _s_. Also Ivan has denoted the _beauty_ of index _i_ as _b__i_, and the _beauty_ of _t_ as the sum of _b__i_ among all indices _i_ such that _s__i_ = _t__i_.\n\nHelp Ivan to determine maximum possible _beauty_ of _t_ he can get."},{"iden":"input","content":"The first line contains one integer _n_ (2 ≤ _n_ ≤ 100, _n_ is even) — the number of characters in _s_.\n\nThe second line contains the string _s_ itself. It consists of only lowercase Latin letters, and it is guaranteed that its letters can be reordered to form an _antipalindromic_ string.\n\nThe third line contains _n_ integer numbers _b_1, _b_2, ..., _b__n_ (1 ≤ _b__i_ ≤ 100), where _b__i_ is the _beauty_ of index _i_."},{"iden":"output","content":"Print one number — the maximum possible _beauty_ of _t_."},{"iden":"examples","content":"Input\n\n8\nabacabac\n1 1 1 1 1 1 1 1\n\nOutput\n\n8\n\nInput\n\n8\nabaccaba\n1 2 3 4 5 6 7 8\n\nOutput\n\n26\n\nInput\n\n8\nabacabca\n1 2 3 4 4 3 2 1\n\nOutput\n\n17"}],"translated_statement":[{"iden":"statement","content":"长度为 #cf_span[m] 的字符串 #cf_span[a] 被称为 _antipalindromic_，当且仅当 #cf_span[m] 为偶数，且对每个 #cf_span[i]（#cf_span[1 ≤ i ≤ m]）都有 #cf_span[ai ≠ am - i + 1]。\n\nIvan 有一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]；#cf_span[n] 为偶数。他希望构造一个字符串 #cf_span[t]，它是 #cf_span[s] 的一个 _antipalindromic_ 排列。此外，Ivan 将索引 #cf_span[i] 的 _beauty_ 定义为 #cf_span[bi]，而字符串 #cf_span[t] 的 _beauty_ 定义为所有满足 #cf_span[si = ti] 的索引 #cf_span[i] 对应的 #cf_span[bi] 之和。\n\n请帮助 Ivan 确定他能得到的最大可能 _beauty_。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100]，#cf_span[n] 为偶数）——字符串 #cf_span[s] 中的字符数。\n\n第二行包含字符串 #cf_span[s] 本身。它仅由小写拉丁字母组成，且保证其字母可以重新排列成一个 _antipalindromic_ 字符串。\n\n第三行包含 #cf_span[n] 个整数 #cf_span[b1], #cf_span[b2], ..., #cf_span[bn]（#cf_span[1 ≤ bi ≤ 100]），其中 #cf_span[bi] 是索引 #cf_span[i] 的 _beauty_。\n\n输出一个数字——#cf_span[t] 可能的最大 _beauty_。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100]，#cf_span[n] 为偶数）——字符串 #cf_span[s] 中的字符数。第二行包含字符串 #cf_span[s] 本身。它仅由小写拉丁字母组成，且保证其字母可以重新排列成一个 _antipalindromic_ 字符串。第三行包含 #cf_span[n] 个整数 #cf_span[b1], #cf_span[b2], ..., #cf_span[bn]（#cf_span[1 ≤ bi ≤ 100]），其中 #cf_span[bi] 是索引 #cf_span[i] 的 _beauty_。"},{"iden":"output","content":"输出一个数字——#cf_span[t] 可能的最大 _beauty_。"},{"iden":"examples","content":"输入8abacabac1 1 1 1 1 1 1 1输出8输入8abaccaba1 2 3 4 5 6 7 8输出26输入8abacabca1 2 3 4 4 3 2 1输出17"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n $ be an even positive integer, $ s \\in \\Sigma^n $ a string over lowercase Latin letters, and $ b \\in \\mathbb{Z}^n $ a vector of beauties.\n\nDefine a permutation $ t $ of $ s $ to be **antipalindromic** if:\n- $ t_i \\ne t_{n-i+1} $ for all $ i \\in \\{1, 2, \\dots, n\\} $.\n\nDefine the **beauty** of $ t $ as:\n$$\n\\sum_{i=1}^n b_i \\cdot \\mathbf{1}_{s_i = t_i}\n$$\n\n**Objective:**  \nMaximize the beauty over all antipalindromic permutations $ t $ of $ s $, given that at least one such permutation exists.\n\n---\n\n**Formal Statement:**\n\nGiven:\n- $ n \\in 2\\mathbb{N} $, $ 2 \\le n \\le 100 $\n- $ s \\in \\Sigma^n $, $ \\Sigma = \\{a, b, \\dots, z\\} $\n- $ b \\in \\mathbb{Z}^n $, $ 1 \\le b_i \\le 100 $\n- $ s $ is such that at least one antipalindromic permutation exists\n\nFind:\n$$\n\\max_{t \\in \\text{Perm}(s),\\; t \\text{ antipalindromic}} \\sum_{i=1}^n b_i \\cdot [s_i = t_i]\n$$\n\nWhere $ \\text{Perm}(s) $ denotes the set of all strings that are permutations of $ s $, and $ t $ is antipalindromic iff $ \\forall i \\in [1, n],\\; t_i \\ne t_{n-i+1} $.","simple_statement":null,"has_page_source":false}