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 N integers . each number will be greater than or equal zero and less that 1000 these are numbers on board

Output

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

Example

Input:
3

0 1 4

3 0 2

1 4 1
Output:
15