E - 分割巧克力

问题描述

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

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

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

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

约束条件

• 1 ≤ H ≤ 10
• 1 ≤ W ≤ 1000
• 1 ≤ K ≤ H × W
• 方块(i, j)的值为0或1

输入

从标准输入中提供的输入数据的格式如下：

H W K

S₁₁S₁₂...S₁W

：

Sₕ₁Sₕ₂...SₕW

输出

打印出最小次数，即需要切割的巧克力棒的次数，以使得每个切块中白色方块的个数不超过K个。

注意事项

在下面提供的所有示例中，每个示例的巧克力棒的形状和所需的切割次数如图所示。

输入1

3 5 4
11100
10001
00111

输出1

2

例如，上图左侧的切割方式可以有效地将巧克力棒切分为满足条件的块。

然而，右侧的两种切割方式都不满足条件。

输入2

3 5 8
11100
10001
00111

输出2

0

不需要切割。

输入3

4 10 4
1110010010
1000101110
0011101001
1101000111

输出3

3