C. Gargari и слоны
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Gargari завидует Caisa, потому что последний прошел игру из прошлой задачи. Теперь Gargari хочет доказать всем, что он самый умный.

У Gargari есть шахматная доска размером n × n. В каждой клетке шахматной доски записано целое число. Gargari хочет разместить на шахматной доске два слона таким образом, что не существует клетки, которая находится под ударом обоих слонов. Рассмотрим клетку доски с числом x, записанным на ней, если она находится под ударом одного из слонов, тогда Gargari получает x долларов за эту клетку. Подскажите Gargari, как разместить двух слонов на доске, чтобы получить как можно больше денег.

Считается, что клетка находится под ударом слона, если она находится на одной диагонали с ним (клетка, в которой стоит слон, также считается находящейся под ударом).

Входные данные

В первой строке записано целое число n (2 ≤ n ≤ 2000). В каждой из следующих n строк записано n целых чисел aij (0 ≤ aij ≤ 109) — описание шахматной доски.

Выходные данные

В первой строке выведите максимальное количество долларов, которое Gargari может заработать. Затем выведите четыре целых числа: x1, y1, x2, y2 (1 ≤ x1, y1, x2, y2 ≤ n), где xi обозначает номер строки, в которой находится i-й слон, yi обозначает номер столбца, в котором находится i-й слон. Считайте, что строки шахматной доски пронумерованы от 1 до n сверху вниз, в столбцы пронумерованы от 1 до n слева направо.

Если есть несколько оптимальных решений, разрешается вывести любое.

Примеры
Входные данные
4
1 1 1 1
2 1 1 0
1 1 1 0
1 0 0 1
Выходные данные
12
2 2 3 2