You are given a N x N square matrix of integers where each cell represents the amount of gold in it. You need to travel from the top left cell to the bottom right cell, and back, maximizing the amount of gold you collect as you pass by the cell following some constraints given below

1. You cannot use squares on the leading diagonal of the matrix (Apart from the top left and the bottom right cells.)

2. When travelling to the bottom right corner from the top left corner, you may only move rightwards or downwards, but never cross the main diagonal.

3. Similarly, while travelling back to the top left corner from the bottom right corner, you may move only leftwards or upwards, but never cross the main diagonal.

Input / Output

The first line contains an integer N denoting the number of rows and columns in the grid.

Then follows N lines where each line contains N integers, where each line denotes the row and each number in each line denotes the column.

Output the maximum gold you can collect, from top left cell to the bottom right cell and back, under the given constraints.