103206: [Atcoder]ABC320 G - Slot Strategy 2 (Hard)
Description
Score : $600$ points
Problem Statement
This problem is a harder version of Problem C, with $N$ reels instead of three and a greater upper limit for $M$.
There is a slot machine with $N$ reels.
The arrangement of symbols on the $i$-th reel is represented by the string $S_i$. Here, $S_i$ is a string of length $M$ consisting of digits.
Each reel has a corresponding button. For each non-negative integer $t$, Takahashi can either choose and press one button or do nothing exactly $t$ seconds after the reels start spinning.
If he presses the button corresponding to the $i$-th reel exactly $t$ seconds after the reels start spinning, the $i$-th reel will stop and display the $((t \bmod M)+1)$-th character of $S_i$.
Here, $t \bmod M$ denotes the remainder when $t$ is divided by $M$.
Takahashi wants to stop all the reels so that all the displayed characters are the same.
Find the minimum possible number of seconds from the start of the spin until all the reels are stopped so that his goal is achieved.
If this is impossible, report that fact.
Constraints
- $1 \leq N \leq 100$
- $1 \leq M \leq 10^5$
- $N$ and $M$ are integers.
- $S_i$ is a string of length $M$ consisting of digits.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $S_1$ $\vdots$ $S_N$
Output
If it is impossible to stop all the reels so that all the displayed characters are the same, print -1.
Otherwise, print the minimum possible number of seconds from the start of the spin until such a state is achieved.
Sample Input 1
3 10 1937458062 8124690357 2385760149
Sample Output 1
6
Takahashi can stop each reel as follows so that $6$ seconds after the reels start spinning, all the reels display 8.
- Press the button corresponding to the second reel $0$ seconds after the reels start spinning. The second reel stops and displays
8, the $((0 \bmod 10)+1=1)$-st character of $S_2$. - Press the button corresponding to the third reel $2$ seconds after the reels start spinning. The third reel stops and displays
8, the $((2 \bmod 10)+1=3)$-rd character of $S_3$. - Press the button corresponding to the first reel $6$ seconds after the reels start spinning. The first reel stops and displays
8, the $((6 \bmod 10)+1=7)$-th character of $S_1$.
There is no way to make the reels display the same character in $5$ or fewer seconds, so print $6$.
Sample Input 2
10 20 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789
Sample Output 2
90
Note that he must stop all the reels and make them display the same character.
Sample Input 3
5 10 0000000000 1111111111 2222222222 3333333333 4444444444
Sample Output 3
-1
It is impossible to stop the reels so that all the displayed characters are the same.
In this case, print -1.
Sample Input 4
10 20 14159265358979323846 26433832795028841971 69399375105820974944 59230781640628620899 86280348253421170679 82148086513282306647 09384460955058223172 53594081284811174502 84102701938521105559 64462294895493038196
Sample Output 4
11
Output
得分：600分
问题描述
此问题是一个比问题C更难的版本，具有$N$个而不是三个卷轴，并且$M$的上限更大。
有一个带有$N$个卷轴的老虎机。
第$i$个卷轴上的符号排列表示为字符串$S_i$。此处，$S_i$是一个由数字组成的长度为$M$的字符串。
每个卷轴都有一个对应的按钮。对于每个非负整数$t$，Takahashi可以在卷轴开始旋转后选择并按下其中一个按钮，或者在$t$秒内不做任何事情。
如果他在卷轴开始旋转后的$t$秒内按下与第$i$个卷轴对应的按钮，则第$i$个卷轴将停止并显示$S_i$的第$((t \bmod M)+1)$个字符。
这里，$t \bmod M$表示$t$除以$M$的余数。
Takahashi希望使所有卷轴停止，以便所有显示的字符相同。
找出从开始旋转到所有卷轴都停止的最短可能时间，以便实现他的目标。
如果不可能实现此目标，请报告该事实。
约束条件
- $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
Takahashi可以通过以下方式使每个卷轴停止，以便在卷轴开始旋转后的6秒内，所有卷轴都显示8。
- 在卷轴开始旋转后的0秒内按下与第二个卷轴对应的按钮。第二个卷轴停止并显示8，这是$S_2$的第$((0 \bmod 10)+1=1)$个字符。
- 在卷轴开始旋转后的2秒内按下与第三个卷轴对应的按钮。第三个卷轴停止并显示8，这是$S_3$的第$((2 \bmod 10)+1=3)$个字符。
- 在卷轴开始旋转后的6秒内按下与第一个卷轴对应的按钮。第一个卷轴停止并显示8，这是$S_1$的第$((6 \bmod 10)+1=7)$个字符。
没有方法可以在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