Задача №1775. Непростая задача
Дана прямоугольная таблица, состоящая из \(m\) строк и \(n\) столбцов. На пересечении \(i\)-й строки и \(j\)-го столбца записано целое число \(a_{ij}\). Требуется найти такие четыре различные ячейки таблицы, чтобы их центры были вершинами прямоугольника со сторонами, параллельными сторонам таблицы, а сумма чисел, записанных в этих ячейках, была максимальна.
На первой строке записаны два натуральных числа \(m\) и \(n\) (2 ≤ \(m\), \(n\) ≤ 500). Далее следует описание таблицы – \(m\) строк, каждая из которых содержит по \(n\) целых чисел (-\(10^7\) ≤ \(a_{ij}\) ≤ \(10^7\)).
На первой строке выходного файла выведите целое число \(r\) – максимальную сумму выбранных элементов, на второй строке выведите 4 натуральных числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) – координаты левой верхней и правой нижней из выбранных ячеек, соответственно (1 ≤ \(x_1\) < \(x_2\) ≤ \(m\), 1 ≤ \(y_1\) < \(y_2\) ≤ \(n\)). Если оптимальных решений несколько, выведите любое.
4 5 7 5 0 7 1 8 9 9 6 7 8 0 2 7 6 7 1 9 2 4
33 2 1 4 3
3 3 5 -4 -2 5 1 -2 5 -8 2
10 1 1 3 3