Задачи
Авангардная архитектура
Авангардная архитектура
Один из столичных девелоперов решил построить жилой дом по проекту известного авангардного архитектора. Жилой дом будет состоять из квартир-кубиков и иметь причудливую форму. Есть два ограничения, одно из которых наложено архитектором, а второе --- законами физики.
Архитектор хочет, чтобы каждый этаж представлял собой связанную последовательность кубиков (разделенные этажи --- это мода \textbf{1990}-х). В то же время необходимо, чтобы хотя бы под одним из кубиков этажа находился кубик предыдущего этажа. Первый этаж должен опираться о землю.
\includegraphics{https://static.e-olymp.com/content/cb/cb4e55d13a4eb069e45570746a121b04946a5a97.jpg}
\includegraphics{https://static.e-olymp.com/content/99/999d57535121330001dd50501db94336d4607044.jpg}
Кроме законов физики архитектора ограничивает также необходимость все это творчество продать. Поскольку покупатели неохотно покупают недвижимость, необходимо привлечь их хоть чем-нибудь, в частности, видом из окна. Специалисты компании-девелопера составили таблицу, в которой для каждого возможного расположения квартиры указана привлекательность вида из окна для этого расположения. Необходимо максимизировать суммарную привлекательность видов из окна.
В приведенном примере показаны привлекательности видов из окна и наилучшее здание из \textbf{10} кубиков в данном случае.
По известному количеству кубиков и таблице привлекательности видов из окна вам необходимо выбрать лучший проект (с максимальной суммарной привлекательностью), удовлетворяющий условиям архитектора и законам физики.
\InputFile
В первой строке входного файла указаны натуральные числа \textbf{N}, \textbf{H} и \textbf{W} (\textbf{1} ≤ \textbf{H}\textit{ }≤ \textbf{30}, \textbf{1} ≤ \textbf{W} ≤ \textbf{30}, \textbf{1} ≤ \textbf{N} ≤ \textbf{HW}) --- количество имеющихся кубиков, максимальная высота и максимальная ширина здания. Следующие \textbf{H} строк содержат по \textbf{W} натуральных чисел, задающих привлекательность соответствующего расположения квартиры. Привлекательность измеряется в пределах от \textbf{1} до \textbf{100 000} включительно.
\OutputFile
Выведите одно число --- наибольшую суммарную привлекательность.
Входные данные #1
10 6 7 9 3 6 4 8 1 3 2 9 2 5 3 2 6 1 1 8 4 6 5 4 1 9 6 5 3 4 5 6 2 5 6 7 1 2 2 6 7 5 6 4 3
Выходные данные #1
65