eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Пірат Джек втомився від битв, мародерства, крадіжок та пригнічення усіх і скрізь у відкритому морі. Він вирішив піти на пенсію, і навіть знайшов ідеальний безлюдний острівець в океані, на якому він гідно проведе залишок життя, якщо у нього, звичайно, не закінчаться гроші. Зараз у нього багато золотих монет, які він хоче скласти у скриню (він же у кінці кінців пірат!). Джек може побудувати скриню у формі прямокутного паралелепіпеда з цілочисельними сторонами, які не перевищують заданий розмір дна скрині. Залишилось лише знайти, куди сховати скриню зі скарбами. Джек вирішив затопити скриню у затишному ставку. Поверхня ставка являє собою прямокут із заданими сторонами, ставок з усіх сторін оточено вертикальними камінними берегами. Джек дослідив дно ставка і знає про кожен квадрат \textbf{1}х\textbf{1} ставка (у декартовій системі координат) глибину ставка у цьому місці. Коли Джек втопить скриню, вона затоне на максимально можливу глибину до тих пір, доки не доторкнеться дна хоча б одним квадратом. Із-за втопленої скрині рівень води у ставку підніметься. Береги ставка достатньо високі, щоб вода ніколи не вилилась за його границі. Зрозуміло, так як скриню потрібно сховати, вона повинна повністю знаходитсь нижче рівня води у ставку. Ваша задача --- знайти максимальний об'єм скрині, яку можна сховтаи у ставку. На рисунку ліворуч показано ставок без скрині, у центрі --- ставок у якому знаходиться скриня об'ємом \textbf{3}, правопуч --- скриня об'ємом \textbf{4} (максимально можливого) у ставку. Зверніть увагу, що якби скриня з центрального рисунка була зроблена на одиницю більшої висоти, то її верх було б видно рівно на поверхні ставка. \includegraphics{https://static.e-olymp.com/content/15/15063c2e6669582a61f2c0534bc97aa50a66aaab.jpg} \textit{\textbf{Рисунок}}: Ілюстрація для вхідного тесту \textbf{1}. \InputFile Вхідні дані містять один тест. Тест починається з рядка, який містить чотири цілих числа \textbf{a}, \textbf{b}, \textbf{m}, \textbf{n }(\textbf{1 }≤ \textbf{a}, \textbf{b}, \textbf{m}, \textbf{n} ≤ \textbf{500}). Розміри поверхні ставка - \textbf{m}×\textbf{n}, максимальний розмір дна скрині - \textbf{a}×\textbf{b}. Кріме того, \textbf{a} та \textbf{b} достатньо малі, щоб скриня ніколи не покрила весь ставок повністю. Кожен з \textbf{m} вхідних рядків, що залишились, містить \textbf{n} чисел \textbf{d_\{i,j\}}, які описують глибину ставка у квадраті з координатами (\textbf{i},\textbf{ j}), де \textbf{0} ≤ \textbf{d_\{i,j\}} ≤ \textbf{10^9} для довільних \textbf{1} ≤ \textbf{i} ≤ \textbf{m}, \textbf{1} ≤ \textbf{j} ≤ \textbf{n}. \OutputFile Виведіть максимальний об'єм скрині з цілочисельними сторонами, який можна сховати у ставку під поверхнею води, причому одне з вимірів дна повинен не перевищувати \textbf{a}, а другий - не перевищувати \textbf{b}. Якщо ніяку скриню не можна сховтаи під водою, то виведіть \textbf{0}.
Ліміт часу 15 секунд
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
3 1 2 3
2 1 1
2 2 1
Вихідні дані #1
4
Джерело ACM-ICPC World Finals 2013