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.

Ivan 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}.

Help Ivan to determine maximum possible beauty of t he can get.


-----Input-----

The first line contains one integer n (2 ≤ n ≤ 100, n is even) — the number of characters in s.

The 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.

The 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.


-----Output-----

Print one number — the maximum possible beauty of t.


-----Examples-----
Input
8
abacabac
1 1 1 1 1 1 1 1

Output
8

Input
8
abaccaba
1 2 3 4 5 6 7 8

Output
26

Input
8
abacabca
1 2 3 4 4 3 2 1

Output
17

Difficulty: VERY_HARD
Tags: Graph algorithms

Flows and cuts

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from collections import Counter
r = lambda : list(map(int, input().split()))

def main():
	(n,) = r()
	s = input()
	cost = list(r())
	ans = 0
	cnt = Counter()
	for i in range(n // 2):
		if s[i] == s[n - 1 - i]:
			ans += min(cost[i], cost[n - 1 - i])
			cnt[s[i]] += 1
	total = sum(cnt.values())
	if total > 0:
		(ch, occ) = cnt.most_common(1)[0]
		avail = []
		if occ > total - occ:
			for i in range(n // 2):
				if s[i] != s[n - 1 - i] and s[i] != ch and (s[n - 1 - i] != ch):
					avail.append(min(cost[i], cost[n - 1 - i]))
			avail.sort()
			ans += sum(avail[:2 * occ - total])
	print(sum(cost) - ans)
main()


class letter(object):

	def __init__(self, let, val):
		self.let = let
		self.val = val

	def __lt__(self, other):
		return self.val < other.val
n = int(input())
s = input()
candi = [[] for i in range(n // 2)]
ans = 0
for (i, vl) in enumerate(map(int, input().split())):
	candi[min(i, n - i - 1)].append(letter(s[i], vl))
	ans += vl
for i in range(n // 2):
	candi[i].sort()
ti = [0 for i in range(26)]
sum = 0
for i in range(n // 2):
	if candi[i][0].let == candi[i][1].let:
		ans -= candi[i][0].val
		ti[ord(candi[i][0].let) - ord('a')] += 1
		sum += 1
mx = 0
p = 0
for i in range(26):
	if ti[i] > mx:
		mx = ti[i]
		p = i
b = []
for i in range(n // 2):
	if ord(candi[i][0].let) - ord('a') != p and ord(candi[i][1].let) - ord('a') != p and (candi[i][0].let != candi[i][1].let):
		b.append(candi[i][0])
b.sort()
i = 0
while mx * 2 > sum:
	sum += 1
	ans -= b[i].val
	i += 1
print(ans)


from collections import *
n = int(input())
s = input()
b = [int(i) for i in input().split(' ')]
n = n
cnt = defaultdict(int)
multiples = []
biggest = 'a'
ans = 0
for i in range(n // 2):
	if s[i] == s[n - i - 1]:
		multiples.append(i)
		cnt[s[i]] += 1
		ans += max(b[i], b[n - i - 1])
	else:
		ans += b[i] + b[n - i - 1]
for i in range(26):
	if cnt[chr(ord('a') + i)] > cnt[biggest]:
		biggest = chr(ord('a') + i)
more = max(max(cnt.values()) * 2 - sum(cnt.values()), 0)
takes = []
for i in range(n // 2):
	if s[i] != s[n - i - 1] and s[i] != biggest and (s[n - i - 1] != biggest):
		takes.append(min(b[i], b[n - i - 1]))
takes = sorted(takes)[:more]
pen = sum(takes)
print(ans - pen)