Задача Место для фабрики Компания, в которой Вы проходите стажировку в качестве аналитика, планирует начать разработку крупного месторождения ценной руды. План месторождения представляет собой прямоугольник размером M × N, разбитый на единичные квадраты — участки. Геологи оценили запасы руды на каждом из участков.
Прежде чем приступать к разработке месторождения, на территории месторождения необходимо построить обогатительную фабрику. Под площадку для постройки фабрики необходимо отвести квадрат из девяти смежных участков, и добыча руды на этом месте будет невозможна.
Вам поручено первое задание — определить такое место для фабрики, при котором количество не добытой из-за её постройки руды будет минимальным.
Формат входных данных
Первая строка содержит два числа M и N (3 ≤ M, N; M ⋅ N ≤ 106, в 80 % тестов величины M и N не превосходят 100). Далее следуют M строк из N чисел каждая — разведанные запасы руды на каждом участке. Эти числа целые, неотрицательные, не превосходящие 100000.
Формат выходных данных
Выведите единственное число — запасы руды на площадке, которую Вы определили для постройки фабрики.
