#P6783. [2019备战noi]blowhard

    ID: 6603 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>难度分类提高动态规划线性 DP计算几何曼哈顿距离变换滚动数组CF2100

[2019备战noi]blowhard

Blowhard

题目描述

Lyra 和 Evan 玩一款有 nn 个关卡、mm 个人物的双人游戏。第 ii 关使用人物 jj 的通关时间为 ti,jt_{i,j}。

每一关,两人都要各自选择一个人物,而且同一关中两人不能使用相同人物。如果在第 ii 关分别选择人物 j1,j2j_1,j_2,则这一关的总用时为

ti,j1+ti,j2.t_{i,j_1}+t_{i,j_2}.

第一关选择人物不消耗时间。从第 ii 关到第 i+1i+1 关时,每个人都可以重新选择人物;一个人从人物 aa 切换到人物 bb 的时间为 k∣a−b∣k|a-b|,保持原人物的费用为 00。两人的切换时间也相加计入总用时。

求通关全部 nn 个关卡的最小总时间。完成最后一关后无需再切换人物。

输入格式

第一行三个正整数 n,m,kn,m,k。

接下来 nn 行,每行 mm 个正整数,第 ii 行第 jj 个整数为 ti,jt_{i,j}。

输出格式

输出一行一个整数,表示最小总用时。若无法按规则完成游戏,输出 -1。

样例输入

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

样例输出

12

数据范围与子任务

所有数据满足 1≤n,m≤3001\le n,m\le300,1≤k,ti,j≤1061\le k,t_{i,j}\le10^6。

子任务 分值 附加限制
1 2121 n,m≤50n,m\le50
2 2929 m≤50m\le50
3 5050 无