Піратська скриня#5658

Піратська скриня

15 секунд

256 мегабайтів

Дуже складна

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

Джек вирішив затопити скриню у тінистому ставку. Поверхня ставка — прямокутник із заданими сторонами, ставок з усіх боків оточено вертикальними кам'яними берегами. Джек дослідив дно ставка й знає для кожного квадрата $1 \times 1$ 1 \times 1 ставка (у декартовій системі координат) глибину в цьому місці. Коли Джек занурить скриню, вона опуститься якомога глибше, доки не торкнеться дна хоча б одним квадратом. Через занурену скриню рівень води у ставку підніметься (навіть якщо немає місця для витісненої води, вона все одно підніме рівень). Береги ставка досить високі, щоб вода ніколи не переливалася за їх межі. Зрозуміло, що скриня має бути невидимою, тобто повністю знаходитися нижче рівня води у ставку. Ваше завдання — знайти максимальний об'єм скрині, яку можна сховати у ставку.

На рисунку зліва показано ставок без скрині, по центру — ставок зі скринею об'ємом $3$ , праворуч — скриня об'ємом $4$ (максимально можлива) у ставку. Зверніть увагу, що якби скриню з центрального зображення зробили на одиницю вищою, її верхівка була б видима рівно на поверхні ставка.

Рисунок: Ілюстрація до вхідного тесту $1$ .

Вхідні дані

Вхідні дані містять один тест. Тест починається з рядка, що містить чотири цілі числа $a$ , $b$ , $m$ , $n$ ( $1 \leq a, b, m, n \leq 500$ 1 \leq a, b, m, n \leq 500). Розміри поверхні ставка — $m \times n$ m \times n, максимальний розмір дна скрині — $a \times b$ a \times b. Крім того, $a$ та $b$ досить малі, щоб скриня ніколи не покривала весь ставок повністю. Кожен із наступних $m$ вхідних рядків містить $n$ чисел $d_{i, j}$ d_{i,j}, що описують глибину ставка у квадраті з координатами $(i, j)$ , де $0 \leq d_{i, j} \leq 1 0^{9}$ 0 \leq d_{i,j} \leq 10^9 для будь-яких $1 \leq i \leq m$ 1 \leq i \leq m, $1 \leq j \leq n$ 1 \leq j \leq n.

Вихідні дані

Виведіть максимальний об'єм скрині з цілими сторонами, яку можна сховати у ставку під поверхнею води, причому один з розмірів дна не повинен перевищувати $a$ , а інший — не перевищувати $b$ . Якщо жодної скрині не можна сховати під водою, виведіть $0$ .

Приклади

Приклад 1