题目描述

We have a chocolate bar partitioned into $H$ horizontal rows and $W$ vertical columns of squares.

The square $(i, j)$ at the $i$-th row from the top and the $j$-th column from the left is dark if $S_{i,j}$ is 0, and white if $S_{i,j}$ is 1.

We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.

How many times do we need to cut the bar so that every block after the cuts has $K$ or less white squares?

我们有一根巧克力棒，它被分成 $H$ 横排和 $W$ 竖列的方格。

如果 $S_{i,j}$ 为 "0"，那么位于从上往下第 $i$ 行和从左往上第 $j$ 列的正方形 $(i, j)$ 是黑色的；如果{2012150}为 "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。

样例 $1$ 解释

例如，在 $1$ -st 和 $2$ -nd行之间以及 $3$ -rd 和 $4$ -th列之间剪切--如左图所示--是有效的。

请注意，我们不能按照右边两幅图所示的方式剪切条形图。

样例 $2$ 解释

无需剪切。