Задача E. Максимальная тройка

Автор:А. Кленин   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

В данном двумерном целочисленном массиве a размером N × N требуется найти три элемента, сумма которых максимальна. При этом первый элемент должен быть соседним по горизонтали или вертикали со вторым, а второй — с третьим.

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

Входной файл содержит число N, за которым следует N2 чисел
a1,1 a1,2a1,N
a2,1 a2,2a2,N
  
aN,1 aN,2aN,N
 — элементы массива.

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

Выходной файл должен содержать единственное число — максимальную сумму. При N = 1 следует вывести единственный элемент матрицы.

Ограничения

1 ≤ N ≤ 2000, 0 ≤ ai,j ≤ 109,

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
3 4
9

0.117s 0.021s 15