kule

문제

Two rooks are to be placed on a chess-like NxN game board. Each square contains a single nonnegative integer. The rooks must be placed on different squares. 

We say that some square on the board is attacked if that square is in the same row or in the same column as one of the rooks. Squares containing the rooks themselves are not considered attacked. 

We want to place our rooks so that the total sum of the numbers on all attacked squares is as large as possible. 

Write a program that will find this maximum sum.

입력

The first line of input contains an integer N, 2 ≤ N ≤ 300. 

Each of the following N lines contains N integers. Each number will be greater than or equal to 0 and less than or equal to 1000. These are the numbers on the board. 

출력

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

3
0 1 4
3 0 2
1 4 1

15

4
0 1 1 1
1 0 4 3
0 1 3 5
0 0 2 5

23

5
4 2 2 3 3
4 2 1 4 0
1 3 4 0 1
4 3 0 2 3
0 0 3 0 4

40