Санта-Клаус очень любит палиндромы. Недавно у него был день рождения. В гости к Санта-Клаусу пришли k друзей, каждый из них подарил ему строку si одной и той же длины n, красота i-й строки равна ai. Возможно, что ai является отрицательным — это значит, что строка не является красивой по мнению Санта-Клауса.
Санта-Клаус без ума от палиндромов. Ему стало интересно: какую максимальную суммарную красоту может иметь палиндром, если склеить какие-то (возможно все) из подаренных строк? Каждый подарок можно использовать не более одного раза. Обратите внимание, что все подаренные строки имеют одинаковую длину n.
Напоминаем, что палиндром — это строка, которая не изменится, если её развернуть задом наперёд.
Так как пустая строка является палиндромом, то искомая максимальная красота — неотрицательна. Даже если все ai отрицательны, Санта-Клаус может получить пустую строку в качестве палиндрома.
Примечание
В первом примере из условия Санта-Клаус может склеить палиндром abbaaaxyxaaabba, используя строки 5, 2, 7, 6, 3 (склеив их именно в этом порядке).