3060 : 贪心进阶-行列快乐值

Coding is the closest thing we have to superpower ！

3060 : 贪心进阶-行列快乐值

描述

给定一个n * m的矩阵，将对矩阵进行k次操作。每次可以进行如下某一种操作：

1.将某行的元素的和累加到快乐值中，然后将该行元素都减去p。

2.将某列的元素的和累加到快乐值中，然后将该列元素都减去p。

问k次之后快乐值总和的最大值是多少？

输入

第一行输入四个整数 $n, m, k, p (1 \le n, m \le 10^3, 1 \le k \le 10^6, 1 \le p \le 10^2)$ 。

接下来n行，每行m个整数表示矩阵。

矩阵中的元素属于区间 $[1, 10^3]$ 。

输出

输出最大快乐值总和。

样例

2 2 2 2
1 3
2 4

5 5 20 100 
464 757 53 708 262 
753 769 189 38 796 
394 60 381 384 935 
882 877 501 615 464 
433 798 504 301 301

2 1 3 2
3 
3

标签

贪心