Cyclic shift of a matrix with maximization of the diagonal sum

Rust Hard loops

Task «Cyclic shift of a matrix with maximization of the diagonal sum»

Given a square matrix of integers of size N x N. In one move, you can cyclically shift any row left or right by an arbitrary number of positions, or cyclically shift any column up or down by an arbitrary number of positions. The goal is to maximize the sum of elements on the main diagonal (from the top-left corner to the bottom-right). Find the maximum possible sum after any number of such operations. N ranges from 1 to 100, matrix elements are integers from -10^6 to 10^6.

Input Format

In the first line, an integer N. Then N lines, each containing N integers separated by spaces.

Output Format

One integer — the maximum sum on the main diagonal.

Examples

Example 1

INPUT

5
1 -2 3 -1 2

OUTPUT

5

Example 2

INPUT

OUTPUT

18

Example 3

INPUT

2
3 4
1 2

OUTPUT

6

main.rs