题目描述

在一堂 IT 课上，Valera 学习了数据压缩。我们现在将向你介绍老师所讲解的一种新的数据压缩方法。

定义压缩函数 $f()$：

• $f($空序列$)=$ 空字符串
• 对于任意一个字符串 $s$，$f(s)=s$。
• 对于任意两个字符串 $s_{1}$，$s_{2}$，$f(s1,s2)$ 为包含前缀 $s_{1}$ 且包含后缀 $s_{2}$ 的字符串中长度最小的一个。
• 对于任意 $n$ 个字符串，$f({s_{1},s_{2},\ldots,s_{n}})=f(f({s_{1},s_{2},\ldots,s_{n-1}}),s_{n})$

例如：

1. $f(001,011)=0011$
2. $f(111,011)=111011$
3. $f(000,000,111)=f(f(000,000),111)=f(000,111)=000111 $

现在 Valera 面临一个难题：他需要将给定的需要压缩的序列 ${a_{1},a_{2},\ldots,a_{n}}$ 分成两个新的序列 ${b_{1},b_{2},\ldots,b_{k}}$ 和 ${c_{1},c_{2},\ldots,c_{m}}$ $(k+m=n)$，使得$S=|f({b_{1},b_{2},\ldots,b_{k}})|+|f({c_{1},c_{2},\ldots,c_{m}})|$ 的值最小。这里 $|p|$ 表示字符串 $p$ 的长度。

注意：

1. 不允许在子序列中更改元素的相对顺序。
2. 可以使得 $mk=0$ 即可以使得序列 $b$、$c$ 中的一个为空。
3. 对于原序列 $a$ 中的任意一项 $a_{i}$，不得既不存在于 $b$ 中，亦不存在于 $c$ 中。也不得同时存在于 $b$ 和 $c$ 中。
4. $b$、$c$ 中的元素在 $a$ 中不必连续，即 $b$ 和 $c$ 的元素可以在 $a$ 中交替出现（参见样例 $2$、$3$）。

输入格式

第一行一个整数 $n$，表示序列 $a$ 的项数。

接下来 $n$ 行，每行一个字符串，第 $i+1$ 行输入的字符串表示序列 $a$ 的第 $i$ 项，即 $a_{i}$。

输入数据保证序列 $a$ 中的所有项长度相同，并且仅由数字 $0$ 或 $1$ 组成。

输出格式

一行一个整数，$S$ 的最小值。

3
01
10
01

4

最佳的方法为：一个子序列为空，另一个子序列等于原始序列 $a$。此时$S_{min}=|f(01,10,01)|=|f(f(01,00),01)|=| f(010,01)|=|0101|=4$。故输出 $4$。

4
000
111
110
001

8

最好的选择是：$b={000,001}$，$c={111,110}$。此时$S_{min}=|f(000,001)|+|f(111,110)|=|0001|+|1110|=8$。故输出 $8$。

5
10101
01010
11111
01000
10010

17

最好的选择是：$b={10101,01010,01000}，c={11111,10010}$。此时$S_{min}=(|10101000 |+|111110010 |=17$。故输出 $16$。