题目描述

在一个神奇的世界里，有一个被称为 ${AC}$ 的公园，拥有着奇妙的魔法力量。公园的土地是一个 ${N}$×${N}$ 的网格，有东西向的行和南北向的列。每个网格的高度都是由神秘的魔法所决定的，用 $A_{i,j}$表示从北边数起第 i 行、从西边数起第 j 列的正方形的高度。

Piggy 是一位年轻的魔法师，决定在 ${AC}$ 公园内创造一个神奇的魔法池塘，池塘的面积是一个 ${K}$×${K}$ 的正方形，其中 ${K}$ 是一个正整数。他希望这个池塘能够成为公园中最神奇的地方，吸引更多的魔法师前来探险。

Piggy 想要在公园内选择一个面积为 ${K}$×${K}$ 的矩形区域，并且该区域内所有正方形的高度的中位数最小。

如果边长是 ${K}$ 的正方形，内部的元素个数就是 ${K}$×${K}$。中位数是指的是这 ${K}$×${K}$ 个数，​按照从大到小排序后​，第 [$\frac{K^2}{2}$]+1 个数。

现在，你需要帮助 Piggy 计算所有可能的 ${K}$×${K}$ 区域中，正方形高度中位数的最小值。只有在找到了这个最小的中位数之后，Piggy 才能开始创造池塘，让公园变得更加有趣。

输入

第一行两个整数，分别代表公园的边长 ${N}$ , 选择区域的边长 ${K}$。

下面的 ${N}$ 行，${N}$ 列，表示每一块小正方形的高度 $A_{i,j}$。

输出

按题意，输出 ${K}$×${K}$ 区域内的最小中位数。

样例

输入复制

3 2
1 7 0
5 8 11
10 4 2

输出复制

4

输入复制

3 3
1 2 3
4 5 6
7 8 9

输出复制

5

说明

【数据范围】

对于 20% 的数据 1≤N≤50。

对于 40% 的数据，1≤N≤400。

对于 100% 的数据，1≤K≤N≤800，0≤$A_{i,j}$≤$10^9$。

输入中的所有值都是整数。

【样例 1 解释】

N = 3 ，K = 2。

1 7 0
5 8 11
10 4 2

所选择正方形数列可能为：

1,7,5,8、7,0,8,11、5,8,10、8,11,4, ,最小的中位数为 4 。

【样例 2 解释】

1,2,3,4,5,6,7,8,9, 中位数是 5 。