EduBrick
← вернуться к уроку · Практика: Клетчатое поле и координаты

Самый лёгкий прямоугольник

8000 мс · 512 МБ · всё или ничего

Дано поле из nn строк по mm чисел и размеры a×ba \times b. Найдите наименьшую сумму чисел в прямоугольнике таких размеров, целиком помещающемся на поле.

Формат ввода

В первой строке числа nn и mm от 11 до 500500, число aa от 11 до nn и число bb от 11 до mm. В следующих nn строках по mm чисел от 109-10^9 до 10910^9.

Формат вывода

Одно число.

Примеры

ввод
2 2 1 1
1 2
3 4
вывод
1
Войдите, чтобы отправлять решения.
← Вернуться к уроку