题目描述

给定一个 $n$ 个卷轴的老虎机，每个卷轴的长度都是 $m$。

从第 $0$ 秒起，老虎机开始转动，在每一秒你最多只可以停下一个卷轴，停止后这个卷轴 不会再转动，也不可以重启。所显示的那个值就是按下停止时的值。（注意：是先选择是否停止，后转动）

求最少需要多少秒，你才可以将这些卷轴全部停下并且让显示的每个值一致？

小提示

1. 一致的值只有 $0\sim 9$ 总共 $10$ 种情况。
2. 卷轴是个环
3. 尝试思考这个问题：$n,m$ 确定的情况下，若的确可以一致，秒数的最大值是多少？
4. 这是题单里面最难的一道题，你可以先看完其他题再来尝试这道题。

输入格式

第一行为两个数 $N,M$。

然后 $N$ 行，每一行为一个长度为 $M$ 的数字串 $S_i$。

输出格式

如果无法一致，则输出 $-1$。

否则输出最少要几秒。

3 10
1937458062
8124690357
2385760149

6

10 20
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789

90

5 10
0000000000
1111111111
2222222222
3333333333
4444444444

-1

10 20
14159265358979323846
26433832795028841971
69399375105820974944
59230781640628620899
86280348253421170679
82148086513282306647
09384460955058223172
53594081284811174502
84102701938521105559
64462294895493038196

11

数据范围

• $1\ \leq\ N\ \leq\ 100$
• $1\ \leq\ M\ \leq\ 10^5$
• $N,M$ 都是整数
• $S_i$ 都是长度为 $M$，且只包含数字字符的串