CF83E Two Subsequences

在一堂 IT 课上，Valera 学习了数据压缩。我们现在将向你介绍老师所讲解的一种新的数据压缩方法。 令 $a_1,a_2,\dots,a_n$ 表示需要压缩的行组成的序列。假设每行长度相等，并且仅由数字 $0$ 和 $1$ 组成，定义压缩函数 $f()$： - $f(\text{空序列})=\text{空字符串}$。 - $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,\ldots,a_n})=f(f({a_1,a_2,\ldots,a_{n-1}}),a_n)$。例如，$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$ 的长度。 不允许在子序列中更改元素的相对顺序。可以让序列 $b$ 和 $c$ 中的一个为空。对于原序列 $a$ 中的任意一项 $a_i$，必须恰好存在于 $b$ 和 $c$ 的一个中。$b$ 和 $c$ 中的元素在 $a$ 中不必连续，即 $b$ 和 $c$ 的元素可以在 $a$ 中交替出现（参见样例 2 和 3）。

第一行一个整数 $n$（$1\le n\le2\cdot10^5$），表示序列 $a$ 的长度。接下来 $n$ 行，每行一个字符串，长度在 $1$ 到 $20$ 之间，且仅由数字 $0$ 或 $1$ 组成。第 $i+1$ 行输入的字符串表示 $a_i$。输入数据保证序列 $a$ 中的所有项长度相同。

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

样例的详细解释如下： - 样例 1 最优方案是将一个子序列设为空，另一个子序列等于整个给定序列。$|f(01,10,01)|=|f(f(01,10),01)|=|f(010,01)|=|0101|=4$。 - 样例 2 最优方案是 $b=\{000,001\},c=\{111,110\}$。$S=|f(000,001)|+|f(111,110)|=|0001|+|1110|=8$。 - 样例 3 最优方案是 $b=\{10101,01010,01000\},c=\{11111,10010\}$。$S=|10101000|+|111110010|= 17$。