#P5354. 开房间

开房间

题目描述

A 和 B 要通过 nn 关。每关有编号 1,…,m1,\ldots,m 的房间,两人各打开一个房间,且同一关两人所选房间必须不同。第 ii 关打开第 jj 个房间需消耗 ti,jt_{i,j} 点体力。

从第二关起,若某人上一关选择 aa 号房间,这一关选择 bb 号房间,他还需额外消耗 K∣a−b∣K|a-b| 点体力。求两人通过全部关卡的最小总消耗。

输入格式

第一行三个整数 n,m,Kn,m,K。接下来 nn 行,每行 mm 个整数。第 ii 行第 jj 个整数为 ti,jt_{i,j}。

输出格式

输出一行一个整数,表示最小总消耗。

样例

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

数据范围

  • 30%30\% 的数据满足 n,m≤5n,m\le5。
  • 60%60\% 的数据满足 n,m≤50n,m\le50。
  • 1≤n≤3001\le n\le300,2≤m≤3002\le m\le300,1≤K,ti,j≤1061\le K,t_{i,j}\le10^6。原 PDF 将 mm 的下界写为 11,现有评测均有至少两个房间。

原 PDF 题面