AT_abc320_g [ABC320G] Slot Strategy 2 (Hard)

[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/A

N/A

### 制約 - $ 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` を出力してください。