Задача №114675. Финальная Битва
Перед началом битвы он должен принести в жертву ровно \(k\) из своих персонажей. После того как все жертвы принесены, на месте каждой из них появится Голем с уроном, равным сумме уронов оставшихся персонажей в соотвутствующих строке и столбце. После этого все персонажи на поле, включая Големов, нанесут по одному удару.
Тайлер ещё не знает, насколько силен главный босс, поэтому ему интересно, какой максимальный суммарный урон он сможет нанести. Помогите ему это посчитать.
В первой строке вводятся три целых числа \(n, m\) и \(k\) (\(1 \le n, m \le 300, 1 \le k \le \min(6, nm)\)) — размеры таблицы и количество жертв, которое необходимо принести.
В каждой из следующих \(n\) строк вводятся \(m\) целых чисел. В \(i\)-й из этих строк на позиции \(j\) вводится число \(a_{ij}\) (\(0 \le a_{ij} \le 2 \cdot 10^5\)) — урон соответствующего персонажа.
Выведите единственное число — максимальный суммарный урон, который смогут нанести персонажи, если оптимальным образом выбрать, кого принести в жертву.
Тесты к этой задаче состоят из 7 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | |||||
| Группа | Баллы | \(n, m\) | \(k\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 8 | – | \(k \le 1\) | ||
| 2 | 11 | – | \(k \le 2\) | 1 | |
| 3 | 19 | – | \(k \le 3\) | 0, 1, 2 | |
| 4 | 14 | \( n, m \le 100\) | \(k \le 4\) | 0 | |
| 5 | 9 | – | \(k \le 4\) | 0 – 4 | |
| 6 | 17 | – | \(k \le 5\) | 0 – 5 | |
| 7 | 22 | – | – | 0 – 6 | Offline-проверка. |
2 3 1 0 6 2 2 3 6
30
2 4 2 4 4 1 1 2 2 9 9
72
2 2 3 12 6 3 9
36