题目描述

农夫约翰的农场被划分为一个 $N \times N$ 的正方形牧场网格（$2 \le N \le 15$）。目前，农场外围有一圈栅栏，但奶牛可以在各个牧场之间自由移动。

农夫约翰决定建造栅栏来把奶牛们隔离开。由于区划法规的限制，每个栅栏必须是一条横跨整个农场的水平或垂直直线，且栅栏不能穿过牧场。约翰只有足够的资金建造至多 $K$ 条栅栏（$1 \le K \le 2N - 2$）。

约翰希望通过建造栅栏，使得划分出的最大奶牛群的规模最小（如果两头奶牛在不穿过任何栅栏的情况下可以互相到达，则它们属于同一群）。给定每个牧场中当前的奶牛数量，请帮约翰计算在最优建造栅栏的情况下，最大奶牛群的规模。

给定一个 $N \times N$ 的矩阵，使用 $K$ 条水平或垂直线来划分矩阵，使得所有区域中元素和的最大值最小。

输入格式

• 第 1 行：两个整数 $N$ 和 $K$。
• 第 $2 \sim 1+N$ 行：每行有 $N$ 个数字，描述农场每一行中每个牧场的奶牛数量（每个牧场至少有 $0$ 头，至多 $1000$ 头奶牛）。

输出格式

• 第 1 行：最大奶牛群规模的可能最小值。

3 2 
1 1 2 
1 1 2 
2 2 4 

4 

提示

农夫约翰应该在第 2 列和第 3 列之间、以及第 2 行和第 3 行之间建造栅栏，这样会产生 4 个群，每个群都有 4 头奶牛。

翻译：Gemini 3.6 Flash