转弯代价的最短路

题目描述

救援车在暴雨后的城市网格中穿梭，街道被划成 $n\times m$ 个路口。每个路口有不同的积水清理时间，车辆每驶入一次就要付出对应时间。此外，方向切换也要耗时：当车辆行驶方向与上一条街不同（由向右转为向下，或由向下转为向右）时，会额外增加一次转弯代价 $T$。车辆从左上角 $(1,1)$ 出发，只能向右或向下行驶到右下角 $(n,m)$。求最小总耗时。

输入格式

第一行包含三个整数 $n,m,T$，表示路网尺寸与单次转弯代价。

接下来 $n$ 行，每行包含 $m$ 个整数，表示各路口的进入耗时。

输出格式

输出一个整数，表示最小总耗时。

输入输出样例 #1

输入 #1

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

输出 #1

11

数据范围

对于 $100\%$ 的数据，$1 \le n,m \le 200$，$0 \le T \le 10^4$，路口耗时满足 $0 \le w_{i,j} \le 10^4$。EOF