Как мы знаем, DZY любит играть. Однажды он решил поиграть с матрицей размера n × m. Точнее, он решил модифицировать матрицу, используя ровно k операций.
Каждая операция может быть одной из двух следующих:
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. После этого матрица будет выглядеть так:
1 10 0
Во втором примере можно выполнить модификации: столбец 2, строка 2, строка 1, столбец 1, столбец 2. После этого матрица будет выглядеть так:
-3 -3-2 -2
2 2 2 2 1 3 2 4
11
2 2 5 2 1 3 2 4
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач