平衡

题号：NC237781
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在古老的大陆上有 $n\times m$ 个区域，它们形成了一个网格图，而区域又分为陆地和湖泊，每个区域 $(i,j)$ 都有一个在 $[-1,10^3]$ 内的权值 $a_{i,j}$ ，若为 $-1$ 则表示当前为湖泊，否则表示人口数量。

你作为这块大陆唯一的守护神，希望人们和平相处，这需要陆地上的人口数量相对平衡。我们定义不平衡值为任意两块相邻的陆地的人口数量之差的最大值。请注意，由于人类智慧（？），所以这里的相邻不是指四连通，与每个区域相邻的区域为它右、上、右上、左、下、左下共六个方向的区域。

由于你是神，所以你有将某个陆地的人口数量加一的能力，但是神力也有上限，你最多只能使用 $k$ 次这个能力。

现在你想要知道，在上述限制下，最小的不平衡值为多少。

第一行三个整数 。
接下来  行，每行  个整数，表示权值。

一个非负整数，表示最小的不平衡值。

示例1

复制

复制

一种可行的方式为
5 4 4
4 -1 6
6 8 8

示例2

复制

11 4 514
19 19 8 10
85 3 96 4
96 4 -1 6
5 4 7 2
-1 0 10 41
4 -1 99 82
44 3 53 -1
14 28 57 -1
12 34 56 78
-1 -1 -1 -1
233 -1 -1 666

复制

，，。
保证至少存在两块相邻的陆地。