B. DZY любит модификации
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Как мы знаем, 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 может получить.

Примеры
Входные данные
2 2 2 2
1 3
2 4
Выходные данные
11
Входные данные
2 2 5 2
1 3
2 4
Выходные данные
11
Примечание

В первом примере можно выполнить модификации: столбец 2, строка 2. После этого матрица будет выглядеть так:


1 1
0 0

Во втором примере можно выполнить модификации: столбец 2, строка 2, строка 1, столбец 1, столбец 2. После этого матрица будет выглядеть так:


-3 -3
-2 -2