マス目の中で白色のマスが連続しているところをひとまとめにしたとき \(n\) 個になり、それぞれ \(x_1, x_2, x_3, \dots x_n\) 個の白マスを含むとします。
幅 \(k\) のハンコを作ったとき以下の事実が分かります

• \(x\) の中に \(k\) より小さい要素があると目標を達成することはできない
• そうでなければ目標は達成できる

また、達成できるとすると最小回数は \(\sum_i \lceil \frac{x_i}{k} \rceil\) です。 (\(\lceil y \rceil\) は \(y\) 以上の最小の整数を表します)
この式は \(k\) に対して広義単調減少なので \(k\) は可能な限り大きいものを使うのがよいです。
よって、 \(k\) を、目標が達成できる最大である \(\min A_i\) として上記の式を計算するとこの問題が解けます。
\(x\) を求めるのは、 \(A\) をソートすると可能で、\(x\) の要素数は \(O(M)\) です。 全体の計算量は、ソートがボトルネックとなって \(O(M \log(M))\) です。