题目描述

给定 $n$ 个 01 串，每次你可以从某个串开头移除一个字符并把它加入一个新串 $S$ 的末尾。最大化 $S$ 中相邻两个字符相同的对数。

输入格式

第一行一个正整数 $n$ 表示串的个数。

接下来 $n$ 行，每行一个 01 字符串。

输出格式

一行一个整数表示答案。

3
0011
0110
1100

9

提示

样例解释

最优方案下，每次取的串的编号为 $1,1,2,1,2,3,1,2,3,2,3,3$，最终的 $S=000111111000$。

数据范围

本题采用捆绑测试

设 $s$ 表示输入的 01 串的长度之和。

对于所有数据，保证 $1\le n\le s\le 10^6$。