Description

小 H 刚收到了一块高 $h$ 宽 $w$ 的矩形巧克力。巧克力的表面被横向 $h - 1$ 条、纵向 $w - 1$ 条的网格线分隔成 $h × w$ 个方格。有的方格是黑巧克力，而有的是白巧克力。

现在小 H 想沿着网格线切割巧克力，将这整块巧克力切分成若干（$\geq 1$）块。\textbf{每一条横向或纵向的网格线，一旦被切割，均只能被从头至尾地完整切割}，不可以只切其中某一段。

他想知道，如果要求切割出来的每块巧克力都包含至多 $k$ 个白巧克力方格，至少需要切割多少条网格线？

Input Format

第一行包含三个正整数 $h$、$w$ 和 $k$，分别表示巧克力的高度、宽度，以及切割出来的每块巧克力所包含的白巧克力方格数上限。

接下来 $h$ 行，每行包含一个长 $w$ 的 01 字符串。其中，从上至下数的第 $i$ 行、从左至右数的第 $j$ 列字符 $s_{i, j}$ 描述对应的巧克力方格。

• 当 $s_{i, j}$ 为字符 0 时，表示对应方格为黑巧克力。

• 当 $s_{i, j}$ 为字符 1 时，表示白巧克力。

Output Format

一个整数，表示至少切割多少条网格线才能满足要求。

  3 5 4
  11100
  10001
  00111

  2

  3 5 8
  11100
  10001
  00111

  0

  4 10 4
  1110010010
  1000101110
  0011101001
  1101000111

  0

Constraints

对于 $10\%$ 的数据，保证 $h = 1$。

对于 $40\%$ 的数据，保证 $1 \leq H \leq 5$。

对于 $100\%$ 的数据，保证 $1 \leq H \leq 10$，$1 \leq W \leq 1000$，$1 \leq K \leq H × W$。