16. Даркстор

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

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

Формат ввода

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

Следующие $N$ строк содержат $M$ чисел $x_{ij}$ $(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

Теги

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