Как мы знаем, DZY любит играть. Однажды он решил поиграть с матрицей размера n × m. Точнее, он решил модифицировать матрицу, используя ровно k операций.
Каждая операция может быть одной из двух следующих:
- Разрешается выбрать некоторую строку матрицы и уменьшить каждый элемент этой строки на p. Такая операция доставляет DZY удовольствие в размере, равном сумме элементов строки до уменьшения.
- Разрешается выбрать некоторый столбец матрицы и уменьшить каждый элемент этого столбца на p. Такая операция доставляет DZY удовольствие в размере, равном сумме элементов столбца до уменьшения.
DZY хочет знать, какое максимальное суммарное удовольствие он может получить, выполнив ровно k модификаций? Пожалуйста, помогите ему посчитать это значение.
Выходные данные
Выведите единственное целое число — максимальное суммарное удовольствие, которое DZY может получить.
Примечание
В первом примере можно выполнить модификации: столбец 2, строка 2. После этого матрица будет выглядеть так:
1 1
0 0
Во втором примере можно выполнить модификации: столбец 2, строка 2, строка 1, столбец 1, столбец 2. После этого матрица будет выглядеть так:
-3 -3
-2 -2
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 2 2
1 3
2 4
|
11
|
|
2
|
2 2 5 2
1 3
2 4
|
11
|