ROOKS - Chess part1

no tags 

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

hide comments
hodobox: 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.

young_padawan: 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

hodobox: 2016-08-03 01:43:14

'square containing a rook is not attacked' -> (2,2) is not added -> 15

Ashwini: 2013-12-20 18:33:17

given test case answer is wrong .It should be 16.
Place rooks at (0,0) and (2,2).

Apoorv Jindal: 2013-11-23 11:08:10

The input file has some wrong test cases.I had to write a wrong program in order to get it AC :/

Aadit Prasad: 2011-03-12 20:15:54

@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.

Code Maestro: 2010-10-01 23:54:23

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..

Luka Kalinovcic: 2010-09-13 21:48:56

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

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