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

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

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

   У наведеному прикладі показано привабливості видів з вікна і найкраща будівля з 10 кубиків у даному випадку.

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

   Вхідні дані

   У першому рядку вхідного файлу задано натуральні числа N, H і W (1 ≤ H ≤ 30, 1 ≤ W ≤ 30, 1 ≤ N ≤ HW) — кількість наявних кубиків, максимальна висота і максимальна ширина будівлі. Наступні H рядків містять по W натуральних чисел, які задають привабливість відповідного розміщення квартири. Привабливість вимірюється в межах відт 1 до 100 000 включно.

   Вихідні дані

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