Compute minimal string segment sizes A common optimization to save space in binaries is to merge string literals where one literal is the suffix of another. For instance, a binary with the string literals

a: foobar
b: bar
c: barbaz
d: foobarbaz
e: baz


might contain the following string literal pool (# representing the \0-terminator):

foobar#foobarbaz#


with the symbols a, b, c, and d having the following values relative to the beginning of the string pool:

a:  0
b:  3
c: 10
d:  7
e: 13


In this task, you have to compute the minimal size of a string pool for a given set of input strings.

Input

The input is a series of up to 999 strings each comprising up to 80 ASCII characters (not including the newline) in the range from 32 to 127 inclusive and then a single newline character.

Output

Find the shortest string such that each of the input strings (including the terminating newlines) are substrings of that string. The output shall be the length of that shortest string. Do not output the string, only its length.

Scoring

This challenge is code golf, standard loopholes apply. The solution with the least length in octets wins.

Examples


Input:

foobar
bar
barbaz
foobarbaz
baz


shortest string, # representing newline:

foobar#foobarbaz#


length: 17
Input:

foobar
foobaz
foobarbaz
barbaz


shortest string, # representing newline:

foobar#foobaz#foobarbaz#


length: 24
Pyth, 20 18 bytes
hljb-{.zsmteM./d.z

Demonstration.
{ can be removed if duplicates are not allowed.
Explanation:
hljb-{.zsmteM./d.z
                .z     The input, as a list of strings.
         m             Map each strings to
             ./d       all possible partitions of the string into separate strings.
           eM          take the last element of each, giving all suffixes.
          t            Remove the first suffix, giving all suffixes other than
                       the string itself.
        s              Sum, combining the list of lists into a single list.
    -{.z               From the set of input strings, remove all suffixes.
                       This is the list of strings in the minimal segment.
  jb                   Join the strings together on newlines.
 l                     Take the length of the resulting string.
h                      Add one and print.