魔法池塘

题目描述

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

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

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

如果边长是 K 的正方形，内部的元素个数就是 K×K。中位数是指的是这 K×K 个数，​按照从大到小排序后​，第 个数。

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

输入格式

第一行两个整数，分别代表公园的边长 NN , 选择区域的边长 KK。

下面的 N 行，N 列，表示每一块小正方形的高度 Ai,j。

输出格式

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

样例输入 #1

3 2
1 7 0
5 8 11
10 4 2

样例输出 #1

4

提示

数据范围

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

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

对于 100% 的数据，1≤K≤N≤800，0≤Aij​≤10^9。

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