Abbreviation
Contest: Codeforces Round 494 (Div. 3)
Difficulty rating: 2200
Tags: dp, hashing, strings

You are given a text consisting of $$$n$$$ space-separated words. There is exactly one space character between any pair of adjacent words. There are no spaces before the first word and no spaces after the last word. The length of text is the number of letters and spaces in it. $$$w_i$$$ is the $$$i$$$-th word of text. All words consist only of lowercase Latin letters.

Let's denote a segment of words $$$w[i..j]$$$ as a sequence of words $$$w_i, w_{i + 1}, \dots, w_j$$$. Two segments of words $$$w[i_1 .. j_1]$$$ and $$$w[i_2 .. j_2]$$$ are considered equal if $$$j_1 - i_1 = j_2 - i_2$$$, $$$j_1 \ge i_1$$$, $$$j_2 \ge i_2$$$, and for every $$$t \in [0, j_1 - i_1]$$$ $$$w_{i_1 + t} = w_{i_2 + t}$$$. For example, for the text "to be or not to be" the segments $$$w[1..2]$$$ and $$$w[5..6]$$$ are equal, they correspond to the words "to be".

An abbreviation is a replacement of some segments of words with their first uppercase letters. In order to perform an abbreviation, you have to choose at least two non-intersecting equal segments of words, and replace each chosen segment with the string consisting of first letters of the words in the segment (written in uppercase). For example, for the text "a ab a a b ab a a b c" you can replace segments of words $$$w[2..4]$$$ and $$$w[6..8]$$$ with an abbreviation "AAA" and obtain the text "a AAA b AAA b c", or you can replace segments of words $$$w[2..5]$$$ and $$$w[6..9]$$$ with an abbreviation "AAAB" and obtain the text "a AAAB AAAB c".

What is the minimum length of the text after at most one abbreviation?

Input format:
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 300$$$) — the number of words in the text.

The next line contains $$$n$$$ space-separated words of the text $$$w_1, w_2, \dots, w_n$$$. Each word consists only of lowercase Latin letters.

It is guaranteed that the length of text does not exceed $$$10^5$$$.

Output format:
Print one integer — the minimum length of the text after at most one abbreviation.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example you can obtain the text "TB or not TB".

In the second example you can obtain the text "a AAAB AAAB c".

In the third example you can obtain the text "AB aa AB bb".

Example input:
6
to be or not to be

Example output:
12

Example input:
10
a ab a a b ab a a b c

Example output:
13

Editorial:
Let $$$eq_{i, j}$$$ equals true if words $$$s_i$$$ and $$$s_j$$$ are equal, otherwise it will be equals false. We can iterate over all pairs of words and compare they just using standard string comparator (constraints are really small so we can do it naively).
The next step is to calculate dynamic programming $$$dp_{i, j}$$$, which will be equal to the maximum length of coinciding segments of words which starts in positions $$$i$$$ and $$$j$$$, respectively. In other words, if $$$dp_{i, j}$$$ equals $$$k$$$, then $$$s[i..i+k-1] = s[j..j+k-1]$$$, word by word. We can calculate this dynamic programming in reverse order ($$$i := n - 1 .. 0, j := n - 1 .. 0$$$) and $$$dp_{i, j} := 0$$$ if $$$s_i \ne s_j$$$, else if $$$i < n - 1$$$ and $$$j < n - 1$$$, then $$$dp_{i, j} := dp_{i + 1, j + 1} + 1$$$, otherwise $$$dp_{i, j} := 1$$$.
Let's keep the length of the text in the variable $$$allsum$$$. Then iterate over all starting positions of the possible abbreviation and all its possible lengths. Let the current starting position will be equals $$$i$$$ (0-indexed) and its length will be equal $$$j$$$. Then we need to calculate the number of possible replacements by its abbreviation. Let it be $$$cnt$$$ and now it equals $$$1$$$. Let's iterate over all positions $$$pos$$$, at the beginning $$$pos = i + j$$$ (0-indexed). If $$$dp_{i, pos} \ge j$$$ then we can replace the segment of words which starts at the position $$$pos$$$ with its abbreviation, so $$$cnt := cnt + 1$$$ and $$$pos := pos + j$$$ (because we cannot replace intersecting segments), otherwise $$$pos := pos + 1$$$.
After this we need to update the answer. The length of the segment of words $$$s[i..j]$$$ can be calculated easily, let it be $$$seglen$$$. Also let $$$segcnt$$$ be the number of words in the current segment of words. Then we can update the answer with the value $$$allsum - seglen * cnt + cnt * segcnt$$$.
Overall complexity is $$$O(n^3 + n \cdot \sum\limits_{i = 0}^{n - 1}|s_i|)$$$, where $$$|s_i|$$$ is the length of the $$$i$$$-th word.