老虎机策略 2（困难版）

题目描述

本题是 Problem C 的困难版本，转轮数为 $N$ 而不是三个，且 $M$ 的上限更大。

有一个带 $N$ 条转轮的老虎机。

第 $i$ 条转轮上的符号排列用字符串 $S_i$ 表示。这里，$S_i$ 是长度为 $M$ 的由数字组成的字符串。

每条转轮都有一个对应的按钮。对于每个非负整数 $t$，高桥可以在转轮开始旋转后恰好 $t$ 秒时，选择按下其中一个按钮，或者什么也不做。

如果他在转轮开始旋转后恰好 $t$ 秒时按下第 $i$ 条转轮对应的按钮，第 $i$ 条转轮就会停止，并显示 $S_i$ 的第 $((t \bmod M)+1)$ 个字符。

这里，$t \bmod M$ 表示 $t$ 除以 $M$ 的余数。

高桥想要停止所有转轮，使得所有显示的字符相同。

求从开始旋转到所有转轮停止且达到目标所需的最少秒数。

如果不可能，报告这一情况。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$S_1$
$\vdots$
$S_N$

输出格式

如果无法使所有转轮停止时显示相同字符，输出 -1。

否则，输出从开始旋转到达到该状态所需的最少秒数。

样例

3 10
1937458062
8124690357
2385760149

6

高桥可以如下停止各条转轮，使得在转轮开始旋转后第 $6$ 秒时，所有转轮都显示 8。

在转轮开始旋转后第 $0$ 秒按下第二条转轮对应的按钮。第二条转轮停止，显示 $S_2$ 的第 $((0 \bmod 10)+1=1)$ 个字符 8。

在转轮开始旋转后第 $2$ 秒按下第三条转轮对应的按钮。第三条转轮停止，显示 $S_3$ 的第 $((2 \bmod 10)+1=3)$ 个字符 8。

在转轮开始旋转后第 $6$ 秒按下第一条转轮对应的按钮。第一条转轮停止，显示 $S_1$ 的第 $((6 \bmod 10)+1=7)$ 个字符 8。

在 $5$ 秒以内不可能使所有转轮显示相同字符，因此输出 $6$。

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

90

注意他必须停止所有转轮并使它们显示相同字符。

5 10
0000000000
1111111111
2222222222
3333333333
4444444444

-1

不可能使所有转轮停止时显示相同字符。

此时输出 -1。

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

11

数据范围

• $1 \le N \le 100$
• $1 \le M \le 10^5$
• $N$ 和 $M$ 是整数。
• $S_i$ 是长度为 $M$ 的由数字组成的字符串。