题目描述

Imagine Bessie's surprise as she spied a leprechaun prancing through the north pasture. Being no one's fool, she charged at the leprechaun at captured him with her prehensile hooves.

'One wish, bovine one. That's all I have for cows,' he said.

'Riches,' Bessie said dreamily. 'The opportunity for riches.'

Leprechauns never grant precisely the easiest form of their captor's wishes. As the smoke cleared from the location of a loud explosion, a shimmering donut spun slowly over the verdant green fields.

'I have made you a torus,' the leprechaun cooed. 'And on that torus is an N x N matrix (1 <= N <= 200) of integers in the range

-1,000,000..1,000,000 that will determine the magnitude of your riches. You must find the sequence of contiguous integers all in one row, one column, or on one diagonal that yields the largest sum from among all the possible sequences on the torus.'

Bessie pondered for a moment and realized that the torus was a device for 'wrapping' the columns, rows, and diagonals of a matrix so that one could choose contiguous elements that 'wrapped around' the side or top edge.

Bessie will share the matrix with you. Determine the value of the largest possible sum (which requires choosing at least one matrix element).

By way of example, consider the 4 x 4 matrix on the left below that has all the elements from one exemplary 'wrapped' diagonal marked:

The marked diagonal of the right-hand matrix includes two nines (the highest available number) and a six for a total of 24. This is the best possible sum for this matrix and includes only three of the four possible elements on its diagonal.

你难以想象贝茜看到一只妖精在牧场出现时是多么的惊讶．她不是傻瓜，立即猛扑过去，用她那灵活的牛蹄抓住了那只妖精．

“你可以许一个愿望，傻大个儿！”妖精说．

“财富，”贝茜用梦游般的声音回答道， “我要获得财富的机会．”

妖精从来没有碰到过这么简单的愿望．他在地方划出一大块N×N(1≤N≤200)的方格，每个格子上写上_1,000,000到1,000,000之间的数字．他说： “在方格上朝一个方向行走，可以是行的方向，列的方向，斜对角的方向，一步只能走一格，所有你踩过的数字的和就是你的财富．”

贝茜请你来帮忙，找到一行、一列或一条对角线上找一段连续的数字，它们的和最大．由于妖精方格的神奇特性，沿着一个方向走，走到了边际，再一步跨过去可以“绕”到方格的对边出现．一行两端的格子是相邻的，一列两端的格子也是相邻的，甚至相邻两行的分别两端的格子也是相邻的（斜对角方向）．

对于下图左边的方格，所有标记过的数字都在一条对角线上．

对于这个方格，能踩出来的最大的和是24，踩过的数字在右图中标记出来了

输入格式

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains N space-separated integers that compose row i of the matrix

输出格式

* Line 1: A single integer that is the largest possible sum computable using the rules above

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

24