AT_abc159_e [ABC159E] Dividing Chocolate

[problemUrl]: https://atcoder.jp/contests/abc159/tasks/abc159_e 縦 $ H $ マス、横 $ W $ マスのグリッドに区切られたチョコレートがあります。 上から $ i $ 行目、左から $ j $ 列目にあるマス $ (i,j) $ のチョコレートは、$ S_{i,j} $ が `0` のとき普通のチョコレートであり、`1` のときホワイトチョコレートです。 このチョコレートに対して、マスの境界に沿った直線によってグリッド全体の端から端まで割る操作を何度か行い、いくつかのブロックに分割します。 分割後のどのブロックにもホワイトチョコレートのマスが $ K $ マス以下しか含まれないようにするためには、最小で操作を何回行う必要があるか求めてください。

N/A

N/A

### 制約 - $ 1\ \leq\ H\ \leq\ 10 $ - $ 1\ \leq\ W\ \leq\ 1000 $ - $ 1\ \leq\ K\ \leq\ H\ \times\ W $ - $ S_{i,j} $ は `0` か `1` ### Sample Explanation 1 例えば左の図のように $ 1 $ 行目と $ 2 $ 行目の間と、$ 3 $ 列目と $ 4 $ 列目の間の $ 2 $ か所で割ればよいです。 右の2つの図のような割り方はできないことに注意してください。 !\[図\](https://img.atcoder.jp/ghi/ac90dd542639c04402125403b1c319d7.png) ### Sample Explanation 2 操作を行う必要はありません。