Description

A君与B君正在玩一款闯关游戏，游戏共有 $n$ 关，每一关的目标只有一个 : 开房间。

每一关都会有 $m$ 个房间，(从 $1 \sim m$ 进行编号)，A君与B君每关各打开一个房间即可过关，但两人不能打开同一个房间。

通过每一关后，$m$ 个房间会重新关上，在第 $i$ 关打开第 $j$ 个房间需要消耗 $t_{i, j}$ 的体力值。并且无论是A君还是B君，除了第一关外，若自己上一关打开了 $a$ 号房间，这一关打开了 $b$ 号房间，则需要额外消耗 $K \times | a - b |$ 点体力值。

现在请你回答，两人通过全部 $n$ 关后所需要消耗的体力值之和最小是多少。

Input Format

第一行三个整数，$n, m, K$

接下来 $n$ 行每行 $m$ 个整数，第 $i$ 行第 $j$ 个数表示 $t_{i, j}$

Output Format

仅一行一个整数表示答案

Sample

样例输入

3 3 10
2 13 4
4 3 2
16 4 3

样例输出

28

Hint

$30 \%$ 的数据，$n, m \leq 5$

$60 \%$ 的数据，$n, m \leq 50$

$100 \%$ 的数据，$1 \leq n, m \leq 300, 1 \leq K, t_{i, j} \leq 10 ^ 6$