该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

在一个大型物流仓库中，小仓正在管理货物的存储和调配工作。仓库被划分成了一个 $n \times m$ 的网格，每个格子代表一个存储单元，里面存放了一定数量的货物。为了优化仓库的资源分配，小仓计划进行 $k$ 次调配操作。

每次调配操作可以选择以下两种方式之一：

1. 清理一整行货物：小仓可以选择某一行，将这一行所有存储单元中的货物减少 $p$。调配之前，这一行中所有货物的总数量会计入小仓的“调配收益”。
2. 清理一整列货物：小仓也可以选择某一列，将这一列所有存储单元中的货物减少 $p$。调配之前，这一列中所有货物的总数量也会计入小仓的“调配收益”。

小仓想知道，通过合理安排 $k$ 次调配操作，他最多可以获得多少“调配收益”。请帮他计算这个值。

输入格式

第一行包含四个整数 $n, m, k, p$，分别表示仓库的行数、列数、调配次数以及每次调配减少的货物数量。

接下来有 $n$ 行，每行包含 $m$ 个整数，表示每个存储单元的初始货物数量 $a_{i,j}$。

数据范围：

• $1 \leq n, m \leq 1000$
• $1 \leq k \leq 10^6$
• $1 \leq p \leq 100$
• $1 \leq a_{i,j} \leq 1000$

输出格式

输出一个整数，表示小仓在 $k$ 次调配操作后可以获得的最大调配收益。

样例

2 2 2 2
1 3
2 4

11

2 2 5 2
1 3
2 4

11

解释

对于样例一：

小仓可以选择“清理第 2 列”和“清理第 2 行”。操作后仓库的存储单元货物数量变为：

1 1
0 0

对于样例二：

小仓连续调配后，仓库的货物数量最终变为：

-3 -3
-2 -2