题目描述

农民约翰的农场被划分成一个N×N的牧场方格（2<=N<=15）。现在，农场外面有围栏，但奶牛可以自由地在牧场之间走动。
农夫约翰决定建造栅栏，把奶牛彼此隔开。由于分区法，每个围栏必须是一条横穿整个农场的水平线或垂直线，围栏不能穿过牧场。农民约翰只有足够的钱建造最多K个篱笆（1<=K<=2N-2）。
农民约翰想建造围栏，以尽量减少由此产生的最大奶牛群的规模（如果两头奶牛不经过任何围栏就能彼此接近，则它们属于同一组）。考虑到目前每个牧场的奶牛数量，如果农民约翰能以最佳方式建造围栏，请帮助他计算出最大奶牛群的规模。

输入格式：

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

输出格式：

第1行：最大奶牛群的最小可能大小。

输入样例#1：

3 2 
1 1 2 
1 1 2 
2 2 4 

输出样例#1：

4