Представьте удивление Bessie, увидевшей лепрекона, скачущего по северному пастбищу. Её не проведёшь: она бросилась на него и схватила цепкими копытами.

«Одно желание, корова. Для коров у меня только это», — сказал он.

«Богатство, — мечтательно сказала Bessie. — Возможность разбогатеть».

Лепреконы никогда не исполняют желания поймавших их самым простым способом. Когда дым громкого взрыва рассеялся, над сочными зелёными полями медленно вращался сияющий пончик.

«Я создал тебе тор, — мягко сказал лепрекон. — На нём матрица $N\times N$ $(1 \le N \le 200)$ целых $-1{,}000{,}000,\ldots,1{,}000{,}000$, определяющая твоё богатство. Из всех последовательностей на торе найди непрерывную последовательность в одной строке, столбце или диагонали с наибольшей суммой».

Подумав, Bessie поняла: тор «замыкает» столбцы, строки и диагонали, позволяя выбирать соседние элементы с переходом через боковой или верхний край.

Bessie поделится матрицей. Найдите наибольшую сумму, выбрав хотя бы один элемент.

Для примера в левой матрице $4\times4$ ниже отмечены все элементы одной замкнутой диагонали:

           8  6  6* 1           8  6* 6  1
          -3  4  0  5*         -3  4  0  5
           4* 2  1  9           4  2  1  9*
           1 -9* 9 -2           1 -9  9*-2

В правой отмечены две девятки (максимальное доступное число) и шестёрка, сумма 24. Это наилучшая сумма, использующая лишь три из четырёх элементов диагонали.

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

• Строка 1: одно целое $N$.
• Строки $2,\ldots,N+1$: строка $i+1$ содержит $N$ целых через пробел, составляющих строку $i$ матрицы.

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

• Строка 1: целое число, наибольшая сумма по этим правилам.

Примеры

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

4
8 6 6 1
-3 4 0 5
4 2 1 9
1 -9 9 -2

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

24

Источник задачи: адаптировано из BOI'98, 2008