Description

小z在玩一个跳跃游戏。游戏平面是一个 H×W 矩阵，每个格子上有一定高度的石柱。小z可以从任意一个格子开始，但他只能向相邻 4个格子跳跃并且跳跃有一定高度限制。设当前所在格子的石柱高度hi，则他可以跳跃到的高度为 [hi−M, hi+M]。每个格子都可以被重复跳到。小z还有一个技能是瞬移。他可以瞬移到任意一个格子。小z想知道，如果他想把每个格子都至少经过一次，需要瞬移的最少次数（开始也算一次瞬移）。

Format

Input

输入第一行为三个整数H，W，M，如题意描述。 接下来 H 行，每行 W 个整数表示格子上石柱的高度。

Output

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

Sample 1

Input

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

Output

3

Limitation

1s, 256MiB for each test case.