Maximum Sum on Grid Lines

You are given an \( n \times n \) grid \( A \) where the element at the \( i\text{-th} \) row and \( j\text{-th} \) column is an integer \( A_{i,j} \). You need to choose one straight line that passes through at least one number in the grid. The line can be chosen from the following types:

• A row
• A column
• A line that is parallel to one of the two diagonal directions (i.e. the main diagonal or the anti-diagonal) and passes only through the grid intersection points

Your task is to find the line for which the sum of the numbers it passes through is maximized, and then output this maximum sum.

Note: The diagonals are defined as follows:

• Main Diagonals: All cells with the same \( i - j = d \) for some integer \( d \) form a diagonal.
• Anti-Diagonals: All cells with the same \( i + j = s \) for some integer \( s \) form an anti-diagonal.

inputFormat

The first line contains a single integer \( n \) (the size of the grid).

Then \( n \) lines follow, each containing \( n \) integers. The \( j\text{-th} \) integer in the \( i\text{-th} \) line represents \( A_{i,j} \).

outputFormat

Output a single integer --- the maximum possible sum of the numbers on a valid line.

sample

3
1 2 3
4 5 6
7 8 9

24