518. Даркстор

Не решаласьСредняя

Петя стажёр в Яндекс Лавке и ему нужно решить задачу по размещению нового даркстора на карте размером NN на MM, где каждая клетка имеет определенное значение прибыли или убытка. Цель Пети - выбрать непустую прямоугольную область на карте, где разместить даркстор будет наиболее выгодно.

Формат ввода

Первая строка содержит два числа NN и MM - размеры карты. (1N,M2001 \le N, M \le 200)

Следующие NN строк содержат MM чисел xijx_{ij} (1iN,1jM,105xij105)(1 \le i \le N, 1 \le j \le M, -10^5 \le x_{ij} \le 10^5) - значение прибыли или убытка для Яндекса в каждой клетке.

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

Выведите одно число - максимальную возможную прибыль.

Ограничения

Ограничение времени

1 с

Ограничение памяти

512 МБ

Пример 1

Ввод
2 2
-2 1
2 4
Вывод
6

Пример 2

Ввод
3 3
1 0 4
2 -1 1
-1 5 2
Вывод
13

Теги

Нужно войти, чтобы отправить решение.Войти