Домино в казино
(Время: 1 сек. Память: 16 Мб Сложность: 72%)
Домино известно в качестве игры, в которую люди обычно играют во дворе, чтобы расслабиться после рабочего дня. Но так было лишь до того времени, пока Джон Бигбак не предоставил возможность играть в домино в своем казино «BUMP» (Bring Us Money, Please).
Обычная игра в домино не совсем подходит для казино, поэтому Джон создал свою собственную игру. Партия играется на прямоугольной доске размера m_n. В каждой ее клетке записано некоторое целое число.
У игрока есть k костей домино - прямоугольников 2×1. Он кладет их на доску так, чтобы не возникало наложений, и его выигрыш вычисляется как сумма произведений чисел, накрытых каждой из костей домино.
Например, существует два способа положить две кости домино на доску размера 2×2. Для доски, приведенной ниже, лучший способ положить домино показан слева - в этом случае сумма составляет 1×3 + 4×2 = 11. Если игрок выберет способ, показанный справа, то сумма составит 1×4 + 3×2 = 10, что меньше чем 11.
По заданному расположению чисел на доске и количеству костей домино, которыми располагает игрок, найдите наибольшую сумму, которую он может получить.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа m, n и k (1 ≤ m ≤ 16, 1 ≤ n ≤ 100, 1 ≤ k ≤ 200). Следующие m строк содержат по n целых чисел каждая и описывают доску. Числа, записанные на доске, неотрицательны и по величине не превосходят 1000. Гарантируется, что существует хотя бы один способ разместить все кости домино на доске.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число - наибольшую сумму, которую может получить игрок.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 2 2
1 4
3 2 | 11 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
