Задача A. Максимальная сумма

Автор:Седьмая Всероссийская Командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:max.in   Ограничение памяти:64 Мб
Выходной файл:max.out  

Условие

Сегодня на страницах газеты "Математический досуг" была опубликована необычная математическая головоломка. Одна из страниц газеты полностью занята прямоугольной таблицей, состоящей из m строк и n столбцов. В каждой ячейке таблицы записано некоторое целое число.

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

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

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

Формат входного файла

На первой строке входного файла записаны два целых числа m и n. Далее следует описание таблицы - m строк, каждая из которых содержит по n целых чисел ai,j.

Формат выходного файла

На первой строке выходного файла выведите целое число s - максимальную сумму чисел на границе искомого прямоугольника. На второй строке выведите четыре натуральных числа: x1, y1, x2, y2 - координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь x - номер строки, а y - номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.

Ограничения

2 ≤ m, n ≤ 300;  − 104 ≤ ai,j ≤ 104

Примеры тестов

Входной файл (max.in) Выходной файл (max.out)
1
2 3
1 1 1
1 1 1
6
1 1 2 3
2
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

0.129s 0.014s 17