配点 : $500$ 点

問題文

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

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

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

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

制約

• $1 \leq H \leq 10$
• $1 \leq W \leq 1000$
• $1 \leq K \leq H \times W$
• $S_{i,j}$ は 0 か 1

入力

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

$H$ $W$ $K$

$S_{1,1}S_{1,2}...S_{1,W}$

$:$

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

出力

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

3 5 4
11100
10001
00111

2

例えば左の図のように $1$ 行目と $2$ 行目の間と、$3$ 列目と $4$ 列目の間の $2$ か所で割ればよいです。

右の2つの図のような割り方はできないことに注意してください。

3 5 8
11100
10001
00111

0

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

4 10 4
1110010010
1000101110
0011101001
1101000111

3