ROOKS - Chess part1

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

Added by:Kawmia Institutes
Date:2010-08-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC VB.NET
Resource:Croatian Highschool Competitions in Informatics 2006

hide comments
2017-07-26 13:48:55
@young_padawan no, you get points for each square attacked by a rook, so you don't for example get the 4 points on squares (3,2) and (1,3) twice, only once.
2016-08-08 16:11:53
for the love of god...this test case makes no sense... for the above set of values the rooks should be placed in (0,1) an (3,3) then we get max sum of 19
2016-08-03 01:43:14
'square containing a rook is not attacked' -> (2,2) is not added -> 15
2013-12-20 18:33:17 Ashwini
given test case answer is wrong .It should be 16.
Place rooks at (0,0) and (2,2).
2013-11-23 11:08:10 Apoorv Jindal
The input file has some wrong test cases.I had to write a wrong program in order to get it AC :/
2011-03-12 20:15:54 Aadit Prasad
@Code Maestro
This is probably too little too late, but 2 1 2 1 2 should give 4 as output. Place the two rooks on the two 'one's.

Last edit: 2011-03-12 20:16:20
2010-10-05 21:14:56 যোবায়ের
@Code Maestro
2 <= N <= 300, so for the sake of maximizing, you won't put 2 rooks in same row or column, but, even if you do so, their place can be attacked by each other, but not by themselves, and no cell is to be counted more than once. And for your case, answer should be 6.
2010-10-01 23:54:23 Code Maestro
a question - if two rooks are in the same row or column, then are their squares counted as being attacked by each other or not?

also, please give answer for:
2
1 2
1 2

thank you..
2010-09-13 21:48:56 Luka Kalinovcic
Please include resource reference when you copy a problem from another site. This problem is from Croatian Highschool Competitions in Informatics 2006. Problem EGYPIZZA is from 2004.
by mohamed maher : added

Last edit: 2010-09-02 15:54:25
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.