众所周知,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列。之后矩阵变为: