[ABC320G] Slot Strategy 2 (Hard)
题意翻译
给定一个 $n$ 个卷轴的老虎机，每个卷轴的长度都是 $m$。
从第 $0$ 秒起，老虎机开始转动，在每一秒你最多只可以停下**一个**卷轴，停止后这个卷轴不会再转动，也不可以重启。所显示的那个值就是按下停止时的值。（**注意：是先选择是否停止，后转动**）
求最少需要多少秒，你才可以将这些卷轴全部停下并且让显示的每个值一致？
题目描述
[problemUrl]: https://atcoder.jp/contests/abc320/tasks/abc320_g
> この問題は 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 $ で割ったあまりを表します。
高橋君は全てのリールを止めた上で、表示されている文字が全て同じであるようにしたいです。
高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを求めてください。
そのようなことが不可能であればそのことを報告してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $ $ S_1 $ $ \vdots $ $ S_N $
输出格式
全てのリールを止めた上で、表示されている文字が全て同じであるようにすることができないなら `-1` を出力せよ。
できるなら、スロットが回り始めてからそのような状態にするまでに最小で何秒かかるか出力せよ。
输入输出样例
输入样例 #1
3 10
1937458062
8124690357
2385760149输出样例 #1
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输入样例 #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 $ の文字列
### Sample Explanation 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 $ を出力します。
### Sample Explanation 2
全てのリールを止めた上で、表示されている文字を揃える必要がある事に注意してください。
### Sample Explanation 3
表示されている文字が全て同じであるようにリールを止めることはできません。 このとき `-1` を出力してください。