题目描述

縦 $H$ マス、横 $W$ マスのグリッドに区切られたチョコレートがあります。

上から $i$ 行目、左から $j$ 列目にあるマス $(i,j)$ のチョコレートは、$S_{i,j}$ が 0 のとき普通のチョコレートであり、1 のときホワイトチョコレートです。

このチョコレートに対して、マスの境界に沿った直線によってグリッド全体の端から端まで割る操作を何度か行い、いくつかのブロックに分割します。

分割後のどのブロックにもホワイトチョコレートのマスが $K$ マス以下しか含まれないようにするためには、最小で操作を何回行う必要があるか求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $K$ $S_{1,1}S_{1,2}...S_{1,W}$ $:$ $S_{H,1}S_{H,2}...S_{H,W}$

输出格式

分割後のどのブロックにもホワイトチョコレートのマスが $K$ マス以下しか含まれないようにするため必要な操作回数の最小値を出力せよ。

题目大意

题意：

有 $H$ 行 $W$ 列的矩形区域，其中每一块是 $0$ 或 $1$

你可以横着切若干刀，然后竖着切若干刀，使每块区域里 $1$ 的总个数 $\le K$ ，求最少总共需要切几刀？

3 5 4
11100
10001
00111

2

3 5 8
11100
10001
00111

0

4 10 4
1110010010
1000101110
0011101001
1101000111

3

提示

制約

• $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つの図のような割り方はできないことに注意してください。 

Sample Explanation 2

操作を行う必要はありません。