/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
この問題は C 問題の強化版です。リールの個数が 3 個から N 個になり、M の上限が大きくなっています。
N 個のリールからなるスロットがあります。
i 番目のリールの配列は文字列 S_i によって表されます。ここで、S_i は数字のみからなる長さ M の文字列です。
それぞれのリールには対応するボタンがついています。高橋君は各非負整数 t について、スロットが回り始めてからちょうど t 秒後にボタンを 1 つ選んで押す、または何もしないことができます。
スロットが回り始めてから t 秒後に i 番目のリールに対応するボタンを押すと、i 番目のリールは S_i の (t \bmod M)+1 文字目を表示して止まります。
ただし、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 秒後に 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
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
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