eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Фотография

Фотография

Каждое утро в 8:30 школьники в ЛКШ собираются на зарядку перед главным корпусом. При этом мальчики и девочки встают на асфальт, образуя прямоугольник.

На крыльце здания стоит фотограф. Он хочет сделать групповую фотографию некоторых мальчиков и девочек. Для этого ему надо выбрать прямоугольную область на асфальте так, что мальчиков и девочек было внутри поровну. К сожалению для ЛКШат, таких областей много. А фотограф хочет сделать фотографии всех областей, чтобы выбрать лучшую. На каждую фотографию у него уходит одна секунда. И все это время мальчики и девочки будут продолжать делать зарядку!

Представим, что на асфальте перед зданием нарисована система координат. Тогда школьники стоят в целочисленных точках, образуя прямоугольник из h × w точек со сторонами, параллельными осям координат. Фотографу необходимо выбрать подпрямоугольник со сторонами, параллельными осям координат.

Напишите программу, которая вычисляет, сколько секунд будут делать зарядку школьники.

Входные данные

Первая строка содержит два натуральных числа h и w (1w, h300) - размеры прямоугольника, образуемого ЛКШатами. В каждой из последующих h строк находятся по w чисел. Число 0 означает, что на очередной позиции стоит мальчик, а число 1 - что на этой позиции стоит девочка.

Выходные данные

Выведите количество секунд, в течение которых будет длиться зарядка.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
3 4
0 1 0 0
1 0 1 1
0 0 0 1
Выходные данные #1
20
Входные данные #2
3 1
0
0
0
Выходные данные #2
0
Автор Олег Пестов
Источник Тринадцатая международная командная олимпиада школьников ЛКШ среди параллелей A, A' и B