嗷呜嗷呜事务所

题目描述

Orange是一只奇美拉小队的管理员，他正带领着 $n \times m$ 只小奇美拉为有需要的人们解决更多麻烦。

这些奇美拉按顺序排列成一个 $n \times m$ 的矩阵 $A$，每只小奇美拉都有一个工作效率 $A_{i,j}$，这意味着，当这只奇美拉每次进行工作时，可以为团队产生 $A_{i,j}$ 点生产力，同时，由于奇美拉自身会因为劳累，而导致工作效率下降 $p$。同时，奇美拉当工作效率降低到负数时，他会因为过度劳累而说怪话，使得团队生产力降低 $|A_{i,j}|$。

Orange共有 $k$ 个任务需要解决，每次任务，Orange可以派遣任意一行或者一列的奇美拉作为一个团队参与工作，这次工作产生的价值为团队中奇美拉的生产力之和。

你的任务是，最大化 $k$ 个任务能够产生的价值之和。

输入格式

输入第一行包含 $4$ 个整数 $n,m,k,p$，表示矩阵大小，任务个数和劳累导致的工作效率下降的值。 接下来为一个 $n \times m$ 的矩阵 $A$，表示每个奇美拉最初的工作效率。

数据范围

$1 \le n \times m \le 10^6$ $1 \le k \le 10^6$ $1 \le p \le 100$ $A_{i,j} \le 1000$

输出格式

输入一个整数，表示所求答案。

样例 #1

样例输入 #1

2 2 2 2
1 3
2 4

样例输出 #1

11

提示

样例解释1

第 1 次，Orange可以派遣第 2 列的奇美拉，此时得到的价值为 $7$，之后奇美拉矩阵变为：

1 1
2 2

第 2 次，Orange可以派遣第 2 行的奇美拉，此时得到的价值为 $4$，之后奇美拉矩阵变为：

1 1
0 0

因此价值之和为 $11$，可以证明这是一种最优的做法。

样例解释2

在样例解释1的基础上，第 3 次，Orange可派遣第 1 行的奇美拉，此时得到的价值为 $2$，之后奇美拉矩阵变为：

-1 -1
0 0

第 4 次，Orange可派遣第 1 列的奇美拉，此时得到的价值为 $-1$，之后奇美拉矩阵变为：

-3 -1
-2 0

第 5 次，Orange可派遣第 2 列的奇美拉，此时得到的价值为 $-1$，之后奇美拉矩阵变为：

-3 -3
-2 -2

因此价值之和为 $11$，可以证明这是一种最优的做法。