Задача D. Весенний поход ≡

Условие

Наступила весна и Даша отправилась в поход, ей надо выбрать место для установки лагеря. Для удобства она мысленно разделила местность на квадраты. У неё получилось n × m квадратов. Некоторые квадраты оказались с лужами, а некоторые с приятным мягким сеном.

И для каждого квадрата она оценила его "приятность", то есть то, насколько бы она хотела ставить лагерь на этот квадрат. Лагерь располагается на прямоугольнике размера h × w блоков.

Помогите Даше определить место расстановки лагеря, сумма приятности квадратов которого максимальна.

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

Первая строка ввода содержит четыре числа n, m, h, w.

Затем идут n строк по m целых чисел в каждом.

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

Вывести одно число — максимальную приятность, которую может получить Даша.

Ограничения

0 < h ≤ n < 10³

0 < w ≤ m < 10³

∑Приятность ≤ 10⁹

Примеры тестов

2 3 2 1
1 0 10
2 3 30

40

Разбор

Задача решается с помощью префиксных (двухмерный случай), так как нам нужно постоянно узнавать сумму в конкретной зоне.

Таким образом перебираются все возможные положения лагеря и сохраняется максимальная приятность.