题目描述

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

有分成纵$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$的白巧克力格。

样例 #1

样例输入 #1

3 5 4
11100
10001
00111

样例输出 #1

2

样例 #2

样例输入 #2

3 5 8
11100
10001
00111

样例输出 #2

0

样例 #3

样例输入 #3

4 10 4
1110010010
1000101110
0011101001
1101000111

样例输出 #3

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块。请注意不能像右边的两张图那样分割。

Sample Explanation 2

不需要进行操作。