Two rooks are to be placed on a chess like N×N game board. Each square contains a single non negative integer. The rooks must be placed on different squares.

We say that some squares on the board are attacked if that square in the same row or same column with the rook but squares containing rooks are not attacked.

We want to place our rooks so that the total sum of the numbers of all attacked squares is as large as possible. write a program that will find this maximum sum.

Input

The first line on input will contain N, 2 <= N <= 300.

Each of the following N lines has N integers. Each number will be greater than or equal to zero and less than 1000, these are the numbers on the board.

Output

The only line should contain a single integer – the maximum sum from the task description.

Example

Input:
3
0 1 4
3 0 2
1 4 1

Output:
15