eolymp
bolt
Try our new interface for solving problems
Məsələlər

Авангардная архитектура

Авангардная архитектура

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Один из столичных девелоперов решил построить жилой дом по проекту известного авангардного архитектора. Жилой дом будет состоять из квартир-кубиков и иметь причудливую форму. Есть два ограничения, одно из которых наложено архитектором, а второе — законами физики.

Архитектор хочет, чтобы каждый этаж представлял собой связанную последовательность кубиков (разделенные этажи — это мода 1990-х). В то же время необходимо, чтобы хотя бы под одним из кубиков этажа находился кубик предыдущего этажа. Первый этаж должен опираться о землю.

Кроме законов физики архитектора ограничивает также необходимость все это творчество продать. Поскольку покупатели неохотно покупают недвижимость, необходимо привлечь их хоть чем-нибудь, в частности, видом из окна. Специалисты компании-девелопера составили таблицу, в которой для каждого возможного расположения квартиры указана привлекательность вида из окна для этого расположения. Необходимо максимизировать суммарную привлекательность видов из окна.

В приведенном примере показаны привлекательности видов из окна и наилучшее здание из 10 кубиков в данном случае.

По известному количеству кубиков и таблице привлекательности видов из окна вам необходимо выбрать лучший проект (с максимальной суммарной привлекательностью), удовлетворяющий условиям архитектора и законам физики.

Giriş verilənləri

В первой строке входного файла указаны натуральные числа N, H и W (1H30, 1W30, 1NHW) — количество имеющихся кубиков, максимальная высота и максимальная ширина здания. Следующие H строк содержат по W натуральных чисел, задающих привлекательность соответствующего расположения квартиры. Привлекательность измеряется в пределах от 1 до 100 000 включительно.

Çıxış verilənləri

Выведите одно число — наибольшую суммарную привлекательность.

Nümunə

Giriş verilənləri #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
Çıxış verilənləri #1
65