Kule
Two rooks are to be placed on a chess-like NxN game board. Each square contains a single non-negative 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.
InputThe 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.
less than or equal to 1000. These are the numbers on the board.
OutputThe first and only line of output should contain a single integer – the maximum sum from the task description.
Input:
Output:
3
0 1 4
3 0 2
1 4 1Output:
15Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.