시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB126654.545%

문제

Дана прямоугольная таблица, состоящая из $m$ строк и $n$ столбцов. На пересечении $i$-й строки и $j$-го столбца записано целое число $a_{ij}$. 

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

입력

На первой строке записаны два натуральных числа $m$ и $n$ ($2 \le m, n \le 500)$. Далее следует описание таблицы --- $m$ строк, каждая из которых содержит по $n$ целых чисел ($-10^7 \le a_{ij} \le 10^7$).

출력

На первой строке выходного файла выведите целое число $r$ --- максимальную сумму выбранных элементов, на второй строке выведите 4 натуральных числа $x_1, y_1, x_2, y_2$ --- координаты левой верхней и правой нижней из выбранных ячеек, соответственно ($1 \le x_1 < x_2 \le m$, $1 \le y_1 < y_2 \le n$). Если оптимальных решений несколько, выведите любое.

예제 입력 1

5 5
1 1 1 1 1
1 2 1 1 1
1 1 1 1 1
1 1 1 3 1
1 1 1 1 1

예제 출력 1

7
2 2 4 4

예제 입력 2

5 5
1 -1 -1 -1 -1
-1 -2 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -3 -1
-1 -1 -1 1 -1

예제 출력 2

0
1 1 5 4