luogu#P2716. 和谐的雪花

和谐的雪花

题目背景

没有背景

题目描述

现在有 n×mn\times m 个雪花,被放在了一个 n ×mn\ \times m 的矩阵当中。每个雪花都有一个优美值。一个正方形的和谐度被定义为在这个正方形中雪花的最大优美值和最小优美值的差,和谐度越大这个正方形就越和谐。现在给出这个矩阵和一个非负整数 kk,zzs 和 zzy 希望你能告诉他,在所有和谐度不小于 kk 的正方形中,边长最小的正方形的边长(即找到一个最小的边长 aa,使得存在一个边长为 aa 的正方形它的和谐度不小于 kk)。如果没有解,输出 1-1

输入格式

第一行两个正整数和一个非负整数,n,mn,mkk

接下来 nn 行,每行 mm 个非负整数,表示题目中的矩阵。

输出格式

如果有解,则输出一个正整数,表示答案。如果无解,则是 1-1

3 5 7
3 4 2 8 7
6 5 2 4 6
3 1 4 0 9
2

提示

数据范围及约定

  • 对于 20%20\% 的数据,1n,m201 \le n,m \le 20
  • 对于 100%100\% 的数据,1n,m5001 \le n,m \le 500
  • 对于 100%100\% 的数据,矩阵中所有数不超过 100000100000