G - Slot Strategy 2 (Hard) 解説 /

実行時間制限: 2 sec / メモリ制限: 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 MtM で割ったあまりを表します。

高橋君は全てのリールを止めた上で、表示されている文字が全て同じであるようにしたいです。
高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを求めてください。
そのようなことが不可能であればそのことを報告してください。

制約

  • 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