AT_abc320_g [ABC320G] Slot Strategy 2 (Hard)

[problemUrl]: https://atcoder.jp/contests/abc320/tasks/abc320_g > 本题是 C 问题的加强版。转盘的数量从 $3$ 个增加到了 $N$ 个，$M$ 的上限也变大了。 有一个由 $N$ 个转盘组成的老虎机。 第 $i$ 个转盘的排列由字符串 $S_i$ 表示，这里 $S_i$ 是一个仅由数字组成、长度为 $M$ 的字符串。 每个转盘上都配有一个对应的按钮。高桥君可以在每个非负整数 $t$ 秒时，选择按下一个按钮，或者什么都不做。 如果在老虎机开始转动后第 $t$ 秒按下第 $i$ 个转盘对应的按钮，则第 $i$ 个转盘会显示 $S_i$ 的第 $(t \bmod M) + 1$ 个字符并停止转动。 其中，$t \bmod M$ 表示 $t$ 除以 $M$ 的余数。 高桥君希望在所有转盘都停止后，显示的字符全部相同。 请你求出，为了达成目标，最少需要多少秒才能让所有转盘都停止且显示相同的字符。 如果无法做到，请输出相应的信息。

输入按以下格式从标准输入读入。 > $N$ $M$ > $S_1$ > $\vdots$ > $S_N$

如果无法让所有转盘都停止且显示相同的字符，则输出 `-1`。 如果可以做到，输出从老虎机开始转动到达成该状态所需的最小秒数。

### 限制条件 - $1 \leq N \leq 100$ - $1 \leq M \leq 10^5$ - $N, M$ 均为整数 - $S_i$ 是仅由数字组成、长度为 $M$ 的字符串 ### 样例解释 1 高桥君可以如下停止各个转盘，使得在老虎机开始转动后第 $6$ 秒时，所有转盘显示的字符都为 `8`。 - 在老虎机开始转动后第 $0$ 秒按下第 $2$ 个转盘的按钮，第 $2$ 个转盘会显示 $S_2$ 的第 $(0 \bmod 10)+1=1$ 个字符，即 `8`，并停止转动。 - 在老虎机开始转动后第 $2$ 秒按下第 $3$ 个转盘的按钮，第 $3$ 个转盘会显示 $S_3$ 的第 $(2 \bmod 10)+1=3$ 个字符，即 `8`，并停止转动。 - 在老虎机开始转动后第 $6$ 秒按下第 $1$ 个转盘的按钮，第 $1$ 个转盘会显示 $S_1$ 的第 $(6 \bmod 10)+1=7$ 个字符，即 `8`，并停止转动。 由于无法在 $5$ 秒及以内让所有转盘显示相同字符，因此输出 $6$。 ### 样例解释 2 请注意，必须在所有转盘都停止后，且显示的字符全部相同。 ### 样例解释 3 无法让所有转盘都停止且显示相同的字符。在这种情况下，请输出 `-1`。 由 ChatGPT 4.1 翻译