题目描述

我们有一个由$H$行和$W$列组成的巧克力棒。

如果第$i$行第$j$列的方块是0，则方块$(i, j)$是黑色的；如果方块$(i, j)$是1，则它是白色的。

我们将切割巧克力棒若干次，以将其切成若干块。每次切割时，我们将整个巧克力棒沿着边界方块的端点切割。

我们需要多少次切割，使得每块切割后的巧克力棒中白色方块的个数不超过$K$个？

输入

第一行输入$H,W,K$

接下来是一个$H$行$W$列的01矩阵

输出

打印出最小次数，即需要切割的巧克力棒的次数，以使得每个切块中白色方块的个数不超过$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