AT_joisc2007_packing3 半導体工場 (Packing)

给定一个大小为 $N \times M$ 的网格，其中每个格子里都有一个整数。你的任务是将这个网格划分成若干个相互连通的块，并满足每个块中所有整数的和不超过 $K$。请计算最少需要多少个这样的连通块。

输入一共有 $N + 1$ 行： - 第一行包含三个整数 $N, M, K$，分别表示网格的行数、列数和连通块中整数和的最大限制。 - 接下来的 $N$ 行，每行包含 $M$ 个整数，代表网格中每个格子里的数值。

输出一个整数，表示最少的连通块数量。

- $1 \le N, M \le 50$ - $1 \le K \le 5000$ - 网格中的每个整数在 $0$ 至 $1000$ 之间（含端点） **本翻译由 AI 自动生成**