Авангардна архітектура#584
Девелопер у столиці вирішив побудувати житловий будинок за проєктом відомого авангардного архітектора. Цей будинок складатиметься з квартир у формі кубів та матиме незвичайний дизайн. Є два основних обмеження: одне встановлене архітектором, інше — законами фізики.
Архітектор вимагає, щоб кожен поверх був єдиною (зв'язаною) послідовністю кубів (відокремлені поверхи — це мода 1990-х). Також хоча б один куб на кожному поверсі має бути безпосередньо підтриманий кубом з нижнього поверху. Перший поверх повинен стояти на землі.
Окрім законів фізики, існує ще й необхідність продати будинок, оскільки покупці нерішуче ставляться до придбання нерухомості й їх треба привабити чимось, наприклад, виглядом з вікон. Фахівці компанії девелопера склали таблицю, яка відображає привабливість вигляду з кожної можливої квартири. Мета — максимізувати сумарну привабливість видів.
На наведеному прикладі показані значення привабливості і найкращий будинок для випадку з кубами.
За заданою кількістю кубів та таблицею привабливості оберіть найкращий дизайн (з максимальною сумарною привабливістю), дотримуючись вимог архітектора та законів фізики.
У першому рядку містяться натуральні числа , , (1 \le H \le 30, 1 \le W \le 30, 1 \le N \le HW) — кількість доступних кубів, максимальна висота та максимальна ширина будинку. Наступні рядків містять по натуральних чисел — значення привабливості для кожної позиції квартири. Привабливість вимірюється від до включно.
Виведіть одне число — максимальну сумарну привабливість.
Приклад 1