Thu thập năng lượng của các hành tinh

Trong một hệ sao xa xôi, các hành tinh được bố trí trên một mạng lưới hình vuông \(n \times n\), \(n\) hàng và \(n\) cột. Các hàng được đánh số liên tiếp theo thứ tự từ \(1\) đến \(n\), các cột được đánh số liên tiếp từ \(1\) đến \(m\) theo thứ tự từ trái sang phải. Trên mạng lưới này, mỗi hành tinh lưu trữ một lượng năng lượng đặc biệt. Hành tinh nằm trên hàng thứ \(i\), cột thứ \(j\) được gọi là hành tinh \((i, j)\), ô này mang giá trị năng lượng năng lượng \(a_{ij}\) \((1 \leq |a_{ij}| \leq 10^9)\).

Đường chéo chính của một mạng lưới (hay bảng hai chiều), chính là dãy các ô \((1, 1), (2, 2), ..., (n, n)\). Phi hành gia của chúng ta đang nghiên cứu các đường bay chéo (tức là các đường chéo chính và các đường chéo song song với nó). Anh ấy phát hiện ra rằng mỗi đường bay như vậy sẽ thu được tổng năng lượng bằng tổng năng lượng của các hành tinh mà nó đi qua.

Ví dụ với mạng lưới \(A\) có kích thước \(4 \times 4\) như sau :

\begincenter
\begintabular | c | c | c | c | \hline
\(2\) & \(3\) & \(2\) & \(4\)
\hline
\(1\) & \(2\) & \(3\) & \(5\)
\hline
\(3\) & \(2\) & \(1\) & \(1\)
\hline
\(4\) & \(1\) & \(3\) & \(2\)
\hline
\endtabular
\endcenter

Ở ví dụ trên, ta có thể thấy \(2\), \(2\), \(1\), \(2\) chính là đường chéo chính, và tổng năng lượng của đường chéo này là \(2 + 2 + 1 + 2 = 7\). Ta có thể thấy, \(3\), \(3\), \(1\) là một đường chéo song song với đường chéo chính, và tổng năng lượng của đường chéo này là \(3 + 3 + 1 = 7\).

Nhiệm vụ của bạn là giúp phi hành gia tìm ra đường bay (đường chéo chính hoặc các đường chéo song song với đường chéo chính) thu được nhiều năng lượng nhất.

Input

Dòng đầu tiên chứa số nguyên \(n\) --- kích thước của mạng lưới hành tinh \((1 \leq n \leq 1000)\).

\(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên \(a_{ij}\) (\(1 \leq |a_{ij}| \leq 10^9\)) --- năng lượng tại hành tinh hàng \(i\), cột \(j\).

Output

In ra một số nguyên --- tổng năng lượng lớn nhất có thể thu được từ một đường bay chéo (tức là một trong các đường chéo song song với đường chéo chính, hoặc đường chéo chính).

Example

4
2 3 3 2
4 1 2 1
2 2 1 2
3 4 3 2

9

Scoring

• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n = 1\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm có \(n \leq 50\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm có \(n \leq 1000\).