Description

小z在玩一个跳跃游戏。游戏平面是一个 $H \times W$ 的矩阵，每个格子上有一定高度的石柱。小z可以从任意一个格子开始，但他只能向相邻 $4$ 个格子跳跃并且跳跃有一定高度限制。设当前所在格子的石柱高度为 $h_i$，则他可以跳跃到的高度为 $[h_i - M, h_i + M]$。每个格子都可以被重复跳到。小z还有一个技能是瞬移。他可以瞬移到任意一个格子。

小z想知道，如果他想把每个格子都至少经过一次，需要瞬移的最少次数（开始也算一次瞬移）。

Input Format

输入第一行为三个整数$H，W，M$，如题意描述。

接下来 $H$ 行，每行 $W$ 个整数表示格子上石柱的高度。

Output Format

输出一行，表示瞬移最少次数。

Sample

样例输入1

3 4 1
2 0 0 0
0 0 2 2
0 0 2 2

样例输出1

3

Hint

对于 $30\%$ 的数据: $H, W \le 10, M \le 10$

对于 $60\%$ 的数据: $H, W \le 300, M \le 50$

对于 $100\%$ 的数据:$H, W \le 500, M \le 256$，所有石柱高度 $\le 256$