分数: 600 点
问题陈述
这个问题是问题 C 的更难版本,其中 N 卷轴而不是三个,并且上限更大 M.
有一台老虎机 N 卷轴。
上符号的排列 i- 第一个卷轴由字符串表示 S_i。在这里, S_i 是一个长度为 M 由数字组成。
每个卷轴都有一个相应的按钮。对于每个非负整数 t,高桥要么选择并按一个按钮,要么什么都不做
卷轴开始旋转后 t 秒。
如果他按下对应的按钮 i-第 卷轴 t 卷轴开始旋转后几秒, i- 第一个卷轴将停止并显示 ((t \bmod M)+1)- 第一个字符 S_i.
在这里, t \bmod M 表示当 t 除以 M.
高桥想要停止所有卷轴,以便所有显示的字符都相同。
找到从旋转开始到所有卷轴停止的最小可能秒数,以便实现他的目标。
如果这是不可能的,请报告这一事实。
约束
- 1 \leq N \leq 100
- 1 \leq M \leq 10^5
- N 和 M 是整数。
- S_i 是一个长度为 M 由数字组成。
输入
输入由标准输入按以下格式给出:
N M S_1 \vdots S_N
输出
如果不可能停止所有卷轴以使所有显示的字符都相同,则打印 -1.
否则,打印从旋转开始到达到这种状态的最小可能秒数。
示例输入 1
3 10 1937458062 8124690357 2385760149
示例输出 1
6
高桥可以按如下方式停止每个卷轴,以便 6 卷轴开始旋转后几秒,所有卷轴显示 8.
- 按第二个卷轴对应的按钮
卷轴开始旋转后 0 秒。第二个卷轴停止并显示
8, ((0 \bmod 10)+1=1)-st 字符 S_2. - 按第三个卷轴对应的按钮
卷轴开始旋转后 2 秒。第三个卷轴停止并显示
8, ((2 \bmod 10)+1=3)-rd 字符 S_3. - 按第一个卷轴对应的按钮
卷轴开始旋转后 6 秒。第一个卷轴停止并显示
8, ((6 \bmod 10)+1=7)- 第一个字符 S_1.
无法使卷轴显示相同的字符 5 或更少秒,因此打印 6.
示例输入 2
10 20 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789
示例输出 2
90
请注意,他必须停止所有卷轴并使它们显示相同的字符。
示例输入 3
5 10 0000000000 1111111111 2222222222 3333333333 4444444444
示例输出 3
-1
不可能停止卷轴以使所有显示的字符都相同。
在这种情况下,打印 -1.
示例输入 4
10 20 14159265358979323846 26433832795028841971 69399375105820974944 59230781640628620899 86280348253421170679 82148086513282306647 09384460955058223172 53594081284811174502 84102701938521105559 64462294895493038196
示例输出 4
11