Build a flow graph where there is a vertex corresponding to each letter of the alphabet and 0.5n vertices corresponding to each pair of letters (s_i, s_{n - 1 - i}). For each letter of the alphabet c, add an edge of capacity 1 to each of the 0.5n vertices, where the cost should be  - max(a_i, a_{n - 1 - i}) if both characters are originally c, cost 0 of neither was equal to c, cost  - a_i if only the i-th character is c and vice versa.

Add an edge of cap cnt_i and cost 0 from sink to each letter, where cnt_i is the frequency of the i-th letter. Add an edge from each vertex denoting a pair with cap 2, cost 0 to sink. It is easy to see that the minimum cost of the min cost max flow is the negative of the answer.

You just add an additional color with 0 balls. Then you can always choose k = 3, and ignore the k = 2 case.

Let us reverse the problem, now we have to merge all the balls into single a box with calculation of answer being same. Greedily, we will pick 3 lowest size of boxes and merge them into a single box. When we are left with only 1 box we are done, but problem is when two boxes remain, now only way is to merge them, but we could do better than this, merge two boxes in the begining because they would weigh less than merging two boxes at end.

Solution: http://mirror.codeforces.com/contest/884/submission/33817504

I think we should make it n % (m - 1) = 1 to get the optimal solution. This way, you'll always use the k = m case to divide.

You can pick the groups as (4,4),(4,4,1),(4)= 21+8+9= 38