AT_abc320_g [ABC320G] Slot Strategy 2 (Hard)

题目描述

本题是 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

输入 #1

3 10
1937458062
8124690357
2385760149

输出 #1

6

输入输出样例 #2

输入 #2

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

输出 #2

90

输入输出样例 #3

输入 #3

5 10
0000000000
1111111111
2222222222
3333333333
4444444444

输出 #3

-1

输入输出样例 #4

输入 #4

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

输出 #4

11

说明/提示

限制条件

• $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 翻译