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

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

HotLog


 

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

(Время: 1 сек. Память: 16 Мб Сложность: 72%)

Домино известно в качестве игры, в которую люди обычно играют во дворе, чтобы расслабиться после рабочего дня. Но так было лишь до того времени, пока Джон Бигбак не предоставил возможность играть в домино в своем казино «BUMP» (Bring Us Money, Please).

Обычная игра в домино не совсем подходит для казино, поэтому Джон создал свою собственную игру. Партия играется на прямоугольной доске размера m_n. В каждой ее клетке записано некоторое целое число.

У игрока есть k костей домино - прямоугольников 2x1. Он кладет их на доску так, чтобы не возникало наложений, и его выигрыш вычисляется как сумма произведений чисел, накрытых каждой из костей домино.

Например, существует два способа положить две кости домино на доску размера 2x2. Для доски, приведенной ниже, лучший способ положить домино показан слева - в этом случае сумма составляет 1x3 + 4x2 = 11. Если игрок выберет способ, показанный справа, то сумма составит 1x4 + 3x2 = 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