CF83E.Two Subsequences

On an IT lesson Valera studied data compression. The teacher told about a new method, which we shall now describe to you.

Let {_a_1, _a_2, ..., a__n} be the given sequence of lines needed to be compressed. Here and below we shall assume that all lines are of the same length and consist only of the digits 0 and 1. Let's define the compression function:

• f(empty sequence) = empty string
• f(s) = s.
• f(_s_1, _s_2) =  the smallest in length string, which has one of the prefixes equal to _s_1 and one of the suffixes equal to _s_2. For example, f(001, 011) = 0011, f(111, 011) = 111011.
• f(_a_1, _a_2, ..., a__n) = f(f(_a_1, _a_2, a__n - 1), a__n). For example, f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111.

Valera faces a real challenge: he should divide the given sequence {_a_1, _a_2, ..., a__n} into two subsequences {_b_1, _b_2, ..., b__k} and {_c_1, _c_2, ..., c__m}, m + k = n, so that the value of S = |f(_b_1, _b_2, ..., b__k)| + |f(_c_1, _c_2, ..., c__m)| took the minimum possible value. Here |p| denotes the length of the string p.

Note that it is not allowed to change the relative order of lines in the subsequences. It is allowed to make one of the subsequences empty. Each string from the initial sequence should belong to exactly one subsequence. Elements of subsequences b and c don't have to be consecutive in the original sequence a, i. e. elements of b and c can alternate in a (see samples 2 and 3).

Help Valera to find the minimum possible value of S.

在一次信息技术课上，瓦莱拉学习了数据压缩。老师介绍了一种新方法，我们现在向你描述该方法。

设 $\{a_1,\,a_2,\,\dots,\,a_n\}$ 为待压缩的一组字符串序列。以下我们均假设所有字符串长度相同，且仅由数字 0 和 1 构成。定义压缩函数 $f$ 如下：

• $f$(空序列) = 空字符串；
• $f(s) = s$；
• $f(s_1,\,s_2)$ = 长度最小的字符串，其某个前缀等于 $s_1$，且某个后缀等于 $s_2$。例如：$f(001,\,011) = 0011$，$f(111,\,011) = 111011$；
• $f(a_1,\,a_2,\,\dots,\,a_n) = f\big(f(a_1,\,a_2,\,\dots,\,a_{n-1}),\,a_n\big)$。例如：
  $f(000,\,000,\,111) = f\big(f(000,\,000),\,111\big) = f(000,\,111) = 000111$。

瓦莱拉面临一个真正的挑战：他需要将给定序列 $\{a_1,\,a_2,\,\dots,\,a_n\}$ 划分为两个子序列 $\{b_1,\,b_2,\,\dots,\,b_k\}$ 和 $\{c_1,\,c_2,\,\dots,\,c_m\}$，其中 $m + k = n$，使得

$$S = \big|f(b_1,\,b_2,\,\dots,\,b_k)\big| + \big|f(c_1,\,c_2,\,\dots,\,c_m)\big|$$

取到最小可能值。这里 $|p|$ 表示字符串 $p$ 的长度。

注意：不允许改变子序列中字符串的相对顺序；允许其中一个子序列为空；初始序列中的每个字符串必须且仅属于其中一个子序列。子序列 $b$ 和 $c$ 中的元素在原序列 $a$ 中不必连续，即 $b$ 和 $c$ 的元素可以在 $a$ 中交替出现（参见样例 2 和 3）。

请帮助瓦莱拉找出 $S$ 的最小可能值。

The first line of input data contains an integer n — the number of strings (1 ≤ n ≤ 2·105). Then on n lines follow elements of the sequence — strings whose lengths are from 1 to 20 characters, consisting only of digits 0 and 1. The i + 1-th input line contains the i-th element of the sequence. Elements of the sequence are separated only by a newline. It is guaranteed that all lines have the same length.

输入数据的第一行包含一个整数 $n$ —— 字符串的个数（$1 \leq n \leq 2\cdot10^5$）。接下来的 $n$ 行依次给出该序列的各个元素 —— 长度为 $1$ 至 $20$ 的字符串，且每个字符串仅由数字 0 和 1 组成。第 $i+1$ 行输入包含序列的第 $i$ 个元素。序列元素之间仅以换行符分隔。保证所有字符串长度相同。

Print a single number — the minimum possible value of S.

输出一个整数——即 $S$ 的最小可能值。

Detailed answers to the tests:

• The best option is to make one of the subsequences empty, and the second one equal to the whole given sequence. |f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4.
• The best option is: b = {000, 001}, c = {111, 110}. S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8.
• The best option is: b = {10101, 01010, 01000}, c = {11111, 10010}. S = |10101000| + |111110010| = 17.

测试题的详细解答：

• 最优方案是使其中一个子序列为空，另一个子序列等于整个给定序列。$|f(01,\,10,\,01)| = |f(f(01,\,10),\,01)| = |f(010,\,01)| = |0101| = 4$。
• 最优方案是：$b = \{000,\,001\}$，$c = \{111,\,110\}$。$S = |f(000,\,001)| + |f(111,\,110)| = |0001| + |1110| = 8$。
• 最优方案是：$b = \{10101,\,01010,\,01000\}$，$c = \{11111,\,10010\}$。$S = |10101000| + |111110010| = 17$。