Задача №111615. Сетка
Карта Байтоландии нанесена на сетку размером \(nm\) (\(n\) – размер по вертикали, \(m\) – по горизонтали). Горизонтальные линии разметки называются параллелями и пронумерованы от 0 до \(n\), вертикальные называются меридианами и пронумерованы от 0 до \(m\) (см. рисунок далее).
Прогнозы погоды – серьезная задача для Байтоландии. Для каждого квадрата сетки требуется определенное время для вычисления прогноза погоды. Из-за особенностей местности и других причин это время может меняться от квадрата к квадрату. До недавнего времени система прогнозирования обрабатывала квадраты один за другим, так что общее время расчета складывалось из суммы времени по каждому квадрату.
Перед вами стоит задача спроектировать новую систему для многопроцессорного компьютера. Чтобы распределить вычисления между процессорами, необходимо поделить Байтоландию r параллелями и s меридианами на (r+1)(s+1) меньших прямоугольников. Каждый процессор будет составлять прогноз для одного прямоугольника и обрабатывать квадраты своего прямоугольника один за другим. Таким образом, время составления прогноза для прямоугольника будет состоять из суммы времени по обработке каждого его квадрата. Временем составления общего прогноза будет максимальное время составления прогноза среди всех прямоугольников.
Ваша задача – найти минимальное возможное время составления прогноза для произвольного деления \(r\) параллелями и \(s\) меридианами.
Первая строка содержит целые числа \(n\), \(m\), \(r\) и \(s\). \(1 \leq r < n \leq 18\), \(1 \leq s < m \leq 18\). Следующие \(n\) строк содержат по \(m\) целых неотрицательных чисел, не превосходящих \(2000000\) — время, требуемое для обработки очередного квадрата сетки.
Выведите минимальное время подсчета.
7 8 2 1 0 0 2 6 1 1 0 0 1 4 4 4 4 4 3 0 2 4 4 4 4 4 3 0 1 4 4 4 8 4 4 0 0 3 4 4 4 4 4 3 0 1 1 3 4 4 3 0 0 0 0 1 2 1 2 0
31