説明のため、\(A,B\) は \(0\)-indexed であるとします。

\(A_i = -A_i \bmod M\) としておくことにより、\(\max_{0 \le i \lt N}((B_i-A_i) \bmod M)\) を最小化する問題に言い換えておきます。

元の \(A,B\) の並び順は答えに影響しないため、あらかじめ \(A,B\) を昇順にソートしておくことにします。

\(O(N \log N + N \log M)\) 解法

結論から言うと、\(\min_{0 \le j \lt N}(\max_{0 \le i \lt N}((B_i-A_{i+j \bmod N}) \bmod M))\) が答えとなります。（つまり、\(A\) の並び替えはサイクリックシフトのみを考えれば良いということです。）この事実の証明は、\(O(N \log N)\) 解法の項を参照してください。

答え \(X\) を二分探索すると、全ての \(i\) について \((B_i-A_{i+j \bmod N}) \bmod M \le X\) であるような \(j\) が存在するかを判定すれば良いです。各 \(B_i\) について注目すると、\(j\) として可能な値の集合は円環上の区間となります。つまり、それらの \(N\) 個の円環上の区間に共通部分が存在するかを求めれば良く、これは累積和などを用いることで \(O(N)\) で求めることが出来ます。また、各 \(i\) についての区間を求める部分は尺取法を用いることで全体で \(O(N)\) で求めることが出来ます。全体の計算量は \(O(N \log N + N \log M)\) です。

\(O(N \log N)\) 解法

\((B_i-A_i) \bmod M\) は、\(A_i \le B_i\) のとき \(B_i-A_i\)、\(A_i \gt B_i\) のとき \(B_i-(A_i-M)\) です。

これを踏まえると、答えが \(X\, (X \lt M)\) 以下であるかの判定が以下のような手順で計算が出来ることが分かります。

1. \(A\) の \(0\) 個以上の好きな要素から \(M\) を引く
2. その後、全ての \(i\) で \(A_i \le B_i \le A_i+X\) が満たされるように \(B\) を並び替えることが出来るかを判定する

2. は、長さの等しい区間と数直線上の点が \(N\) 個ずつ与えられた時、全てのペアにおいて区間内に点が存在するように区間と点をマッチングする問題であり、これは明らかに \(A,B\) の昇順に順番通りマッチさせるのが最適です。

また、\(M\) を引く \(A\) の個数 \(k\) を決め打った時、\(A_i\) の降順に \(k\) 個選んで \(M\) を引くのが最適です。\(B_i\) が \([0,M)\) に収まっているため、各区間について \([A_i,A_i+X]\) と \([0,M)\) の共通部分を取って良いことに注目すると、この選び方が他の選び方よりも真に良いことが示せます。

これを踏まえてさらに言い換えると、以下の手順で得られる値の最小値が答えであることが分かります。

1. \(B'_0, B'_1, \dots , B'_{2N-1}\) を \(B_0, B_1, \dots , B_{N-1}, B_0+M, B_1+M, \dots, B_{N-1}+M\) とする
2. \(0 \le k \le N\) かつ、全ての \(i\) について \(A_i \le B'_{i+k}\) を満たすような \(k\) を選ぶ
3. \(\max_{0 \le i \lt N}(B'_{i+k}-A_i)\) を求める

3. で求める値が \(k\) に対して単調増加であることから、2. では条件を満たすもののうち最小の \(k\) を選ぶのが最適です。\(k\) を二分探索することで、\(O(N \log N)\) で答えを求めることが出来ます。（コード）