At a glance, it may seem that it needs an exponential time to solve it, and actually it is impossible to find the answer if you construct a string from one side, as there are infinite number of possibilities.

For example, when checking if a string is a palindrome, you can judge by removing the corresponding outer characters if they are the same, and denying if they are not the same.

In the method mentioned above, you do not have to know the length of the string, and let us try utilizing this method.

We consider constructing a string from the “leftmost and rightmost” parts. First, both the left and the right are empty.

Consider appending one of given strings to the left or the right in the intermediate state. Here, if it does not consistent with the unmatched part, the transition is impossible.

Extending by this method requires only to hold the string that is not still a palindrome, but there are still infinite states.

Now, let us consider appending strings only to the opposite side of which a string is remaining. Then, the remaining string should appear as either the prefix or suffix of the given strings.

Therefore, we could restrict the number of remaining strings to \(2N \max |S_i|\), so all that left is to regard those strings as vertices and use Dijkstra method to find the distances to empty string / palindromes, the cost of whose transitions are \(C_i\). Even if the comparison are done naively, the time complexity is \(\mathrm{O}(N^2 L (L + \log NL))\) where \(L := \max |S|\), which is fast enough.

Sample Code(C++)