分巧克力

题目描述

有一块被分成纵 $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$ 格,所需切割次数的最小值。

样例

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

数据范围

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