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: interview

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()


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)
# print(more)
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(pen)
# print(takes)
print(ans-pen)


#https://pymotw.com/2/collections/counter.html
#same code as mmaxio
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:# if highest occurence is more than the 50% of total then we will look for the letters which does not have pairs and are not equal to the letter with the highest ocuurence
			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()
#suppose total is 100 and highest occ is 51...difference between highest occ and remaining can be found using this form 2*occ-total as it is a simplified form of two steps 1.total-occ=remaining and 2.occ-remaining which is this case is 2 if highest occ is <= 50 % of total then it can be satisfied by remaining 50% but if it is greater than 50% then we have to use the letters of of the total


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)