410559: GYM104049 K Fullmetal Alchemist II

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Fullmetal Alchemist IItime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

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

ExamplesInput
3
abcd
defg
fghi
Output
9
Input
4
woofer
floofer
error
two
Output
17

加入题单

上一题 下一题 算法标签: