3869: 陈晫选数2

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:3 通过:2

题目描述

      陈晫再次找了到了一个 n*m 的矩阵,这个矩阵上都填有一些数字,对于第 i 行第 j 列的位置上
的数为 ai,j。 

     由于陈晫 已经AK 了 近10年noip 的初赛和复赛题了,最近又显得非常无聊,开始自己编游戏。
它想到的游戏是这样的: 每次选择一行或者一列, 它得到的快乐值将会是这一行或者一列的
数字之和。之后它将该行或者该列上的数字都减去 p(之后可能变成负数) 。如此,重复 k
次,它得到的快乐值之和将会是它 NOIP2022 复赛比赛时的 RP 值。
陈晫 当然想让它的 RP 值尽可能高,于是它来求助于你。 

输入格式

第一行 4 个数 n,m,k,p。
接下来 n 行 m 列,表示 ai,j。
对于所有数据 1<=n,m<=1000,k<=1000000,1<=ai,j<=1000,0<=p<=100。

输出格式

输出一行表示最大 RP 值。

输入样例 复制

2 2 5 2
1 3
2 4

输出样例 复制

11

数据范围与提示

第一次选择第二列,第二次选择第二行,第三次选择第一行,第四次选择第二行,第五
次选择第一行,快乐值为 7+4+2+0+-2=11

分类标签