题目描述

$\red{Farmer John }$的农场分为 $\red{N x N }$方格的牧场 $\red{(2 <= N <= 15)}$。现在，农场外面有一道栅栏，但奶牛可以在牧场之间自由移动。

农夫约翰决定建造栅栏将奶牛彼此隔开。由于分区法，每个栅栏必须是横穿整个农场的水平线或垂直线，并且栅栏不能穿过牧场。$\red{Farmer John }$只有足够的钱来建造最多 $\red{K }$个栅栏 $\red{(1 <= K <= 2N - 2)}$。

$\red{Farmer John }$想要建造栅栏，以最小化由此产生的最大奶牛群的大小（如果两只奶牛可以在不穿过任何栅栏的情况下相互接触，则它们属于同一群）。给定每个牧场的当前奶牛数量，帮助 $\red{Farmer John }$计算最大奶牛群的规模（如果他以最佳方式建造围栏）。

给出一个$\red{n\times n}$的矩阵，用$\red{k}$条水平或竖直直线分割矩阵，最小化区域和最大值。

输入格式

第 $\red{1 }$行：两个整数，$\red{N }$和 $\red{K}$

第 $\red{2..1+N }$行：每行有 $\red{N }$个数字，描述农场一排每个牧场的奶牛（每个牧场至少有 $\red{0 }$头，最多 $\red{1000 }$头奶牛）

输出格式

第 $\red{1 }$行：最大奶牛群的最猩能规模。

样例

输入样例

3 2 
1 1 2 
1 1 2
2 2 4

输出样例

4

提示

$\red{Farmer John }$应该在第 $\red{2 }$列和第 $\red{3 }$列之间以及第 $\red{2 }$行和第 $\red{3 }$行之间建立栅栏，这将创建 $\red{4 }$个组，每个组有 $\red{4 }$头奶牛。