Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Домино в казино

(Время: 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.TXTOUTPUT.TXT
12 2 2
1 4
3 2
11

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483