Chạy tiếp sức

Cho một bảng vuông kích thước $n\times n$. Ô nằm ở hàng $i$, cột $j$ chứa số nguyên $a_{i,j}$.

Hai vận động viên chạy tiếp sức trên bảng này. Người thứ nhất xuất phát từ ô $(1,1)$ và chạy tới ô $(n,n)$: khi đang đứng ở ô $(i,j)$, anh ta chỉ được chuyển sang ô $(i+1,j)$ hoặc ô $(i,j+1)$. Ngay khi người thứ nhất tới đích, người thứ hai xuất phát từ ô $(n,n)$ và chạy về ô $(1,1)$: khi đang đứng ở ô $(i,j)$, anh ta chỉ được chuyển sang ô $(i-1,j)$ hoặc ô $(i,j-1)$. Cả hai người đều không được đi ra ngoài bảng.

Điểm của đội bằng tổng các số ghi trên những ô mà ít nhất một trong hai người đã đi qua. Một ô mà cả hai người cùng đi qua chỉ được tính đúng một lần.

Hãy tìm số điểm lớn nhất mà đội có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $n$.
• $n$ dòng tiếp theo, mỗi dòng chứa $n$ số nguyên; số thứ $j$ trên dòng thứ $i$ là $a_{i,j}$.

Dữ liệu ra

Một số nguyên duy nhất: số điểm lớn nhất đạt được.

Ràng buộc

• $1\le n\le 300$
• $-1000\le a_{i,j}\le 1000$

Ví dụ