题目描述

我们有一块被分成 $H$ 行 $W$ 列的巧克力棒。

如果第 $i$ 行第 $j$ 列的方块是黑色，那么 $S_{i,j}$ 等于 0；如果是白色，那么 $S_{i,j}$ 等于 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$。

示例输入 1

3 5 4
11100
10001
00111

示例输出 1

2

例如，我们可以在第 $1$ 行和第 $2$ 行之间，在第 $3$ 列和第 $4$ 列之间切割，如左侧图示所示。

请注意，右侧图示的切割方式是不可行的。

示例输入 2

3 5 8
11100
10001
00111

示例输出 2

0

不需要切割。

示例输入 3

4 10 4
1110010010
1000101110
0011101001
1101000111

示例输出 3

3