← 返回题目列表

Codeforces · 446/B

B. DZY 爱改装

中文机器翻译题面 查看原题

众所周知,DZY喜欢玩游戏。有一天,DZY 决定使用一个 n × m 矩阵。更准确地说,他决定用恰好 k 次运算来修改矩阵。

每个修改都是以下之一:

1. 选择矩阵的某行并将该行的每个元素减少 p。这个操作给DZY带来的快乐值等于递减之前的行元素之和。
2. 选择矩阵的某列并将该列的每个元素减少 p。这个操作给DZY带来的快乐值等于递减前的列元素之和。

DZY想知道:在执行k次修改后,他能获得的最大快乐值是多少?请帮他计算一下这个值。

输入

第一行包含四个空格分隔的整数 n、m、k 和 p (1 ≤ n, m ≤ 103; 1 ≤ k ≤ 106; 1 ≤ p ≤ 100)。

接下来是 n 行。它们每个都包含 m 个整数,代表 aij (1 ≤ aij ≤ 103) — 矩阵当前行的元素。

输出

输出一个整数——DZY 可以获得的最大可能的总快乐值。

示例

输入 #1

2 2 2 2
1 3
2 4

输出 #1

11

输入 #2

2 2 5 2
1 3
2 4

输出 #2

11

注意

对于第一个样本测试,我们可以修改:第2列,第2行。之后矩阵变为:

对于第二个样本测试,我们可以修改:第2列,第2行,第1行,第1列,第2列。之后矩阵变为: