AT_abc159_e [ABC159E] Dividing Chocolate

有一块被划分为高 $H$ 行、宽 $W$ 列的网格状巧克力。 对于第 $i$ 行第 $j$ 列的格子 $(i, j)$，如果 $S_{i,j}$ 为 `0`，则该格子是普通巧克力；如果为 `1`，则是白巧克力。 你可以多次沿着格子的边界，从网格的一端到另一端画直线，将整块巧克力分割成若干块。 请你求出，最少需要进行多少次这样的分割操作，才能使得分割后的每一块中，包含的白巧克力格子的数量都不超过 $K$。

输入通过标准输入给出，格式如下： > $H$ $W$ $K$ > $S_{1,1}S_{1,2}\ldots S_{1,W}$ > $S_{2,1}S_{2,2}\ldots S_{2,W}$ > $\vdots$ > $S_{H,1}S_{H,2}\ldots S_{H,W}$

输出一个整数，表示为了满足每一块中白巧克力格子的数量都不超过 $K$，所需的最小分割操作次数。

### 限制条件 - $1 \leq H \leq 10$ - $1 \leq W \leq 1000$ - $1 \leq K \leq H \times W$ - $S_{i,j}$ 仅为 `0` 或 `1` ### 样例解释 1 例如，可以如左图所示，在第 $1$ 行与第 $2$ 行之间，以及第 $3$ 列与第 $4$ 列之间各切一刀，共 $2$ 次分割即可。 注意，右侧两种分割方式是不允许的。  ### 样例解释 2 无需进行任何分割操作。 由 ChatGPT 4.1 翻译