Задачі
Авангардна архітектура
Авангардна архітектура
Один зі столичних девелоперів вирішив побудувати житловий будинок за проектом відомого авангардного архітектора. Житловий будинок буде складатись з квартир-кубиків і мати причудливу форму. Є два обмеження, одне з яких накладено архітектором, а друге --- законами фізики.
Архітектор хоче, щоб кожен етаж являв собою зв`язану послідовність кубиків (відокремлені поверхи --- це мода \textbf{1990}-х). У той же час необхідно, щоб хоча б під одним з кубиків поверху знаходився кубик попереднього поверху. Перший поверх повинен спиратись на землю.
\includegraphics{https://static.e-olymp.com/content/7a/7a7a76c27a055781f05e8a37a516d7cabe59f3ed.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