410559: GYM104049 K Fullmetal Alchemist II

The only differences between the first and second versions are constraints on the number and length of strings given as input. This problem has larger upper bounds.

Edward and Alphonse Elric are exploring a recently discovered branch of alchemy created by the people of Xerxes. Rather than using transmutation circles, Xerxians used spoken phrases to facilitate alchemic reactions. Each phrase that can be used to perform Xerxian alchemy can be written as a string comprised of only lowercase alphabetical characters.

The primary property of interest when it comes to Xerxian alchemy is the theory behind creating multiple simultaneous reactions. A single phrase can kickstart any reaction whose written form is contained as a substring within the phrase string.

Remembering many phrases is difficult for the Elric brothers, so they would instead like to remember a single, potentially longer phrase that can perform all of the $$$N$$$ alchemic reactions that they know. To help with memorization, the Elrics want to minimize the length of the new phrase string. You, an expert programmer, (an alchemist in your own right), must help the Fullmetal Alchemist find the minimal length of such phrase.

The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10$$$), representing the number of phrases that the Elric brothers know. The next $$$N$$$ lines of input each contain a string $$$s_i$$$ ($$$1 \leq |s_i| \leq 10^4$$$), representing a reaction the Elric brothers want to incorporate into their new phrase. Note that these reactions do not necessarily have distinct written forms.

Output a single integer representing the minimal length of the single phrase containing all the given phrases.

3
abcd
defg
fghi

9

4
woofer
floofer
error
two

17