ヒント \(\rightarrow\) https://atcoder.jp/contests/arc176/editorial/9825

\(S_k\) を \(i + j = k \bmod N\) を満たすマス \((i,j)\) の集合とします。さて、\(S_k\) から相異なるように \(M\) 個選びそこに含まれるマスに \(1\) を書き込むと行和、列和が \(M\) になります。

あとは各 \(i\) に対して \(S_{A_i + B_i \bmod N}\) を含めばよく、これは簡単に達成できます。\(A_i + B_i \bmod N\) に重複がある場合 \(S_k\) を追加する必要があることに注意してください。

実装例