Задача №409. Максимальная сумма
Сегодня на страницах газеты «Математический досуг» была опубликована необычная математическая головоломка. Одна из страниц газеты полностью занята прямоугольной таблицей, состоящей из m строк и n столбцов. В каждой ячейке таблицы записано некоторое целое число.
Для решения головоломки требуется найти такой невырожденный прямоугольник с вершинами в центрах ячеек таблицы, и сторонами, параллельными сторонам таблицы, чтобы сумма чисел, записанных в ячейках на границе получившегося прямоугольника, была максимальна.
Безуспешно потратив несколько часов на решение головоломки, Саша решил написать программу, которая сделала бы это за него. Но и тут его постигла неудача. Теперь ему ничего не остается, как обратиться за помощью к вам.
Напишите программу, которая по заданной таблице найдет искомый прямоугольник.
В первой строке вводятся два целых числа \(m\) и \(n\) (\(2 \le m, n \le 300\)). Далее следует описание таблицы – \(m\) строк, каждая из которых содержит по \(n\) целых чисел \(a_{i, j}\) (\(-10^4 \le a_{i,j} \le 10^4\)).
В первой строке выведите целое число \(s\) – максимальную сумму чисел на границе искомого прямоугольника. Во второй строке выведите четыре натуральных числа: \(x_1\), \(y_1\), \(x_2\), \(y_2\) – координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь \(x\) – номер строки, а \(y\) – номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.
2 3 1 1 1 1 1 1
6 1 1 2 3
5 4 9 -2 -1 3 -10 -5 1 -4 1 -1 2 -2 3 0 0 -1 2 2 -1 2
8 3 1 5 3