Deslocamento cíclico de matriz com maximização da soma da diagonal

Rust Hard loops

Tarefa «Deslocamento cíclico de matriz com maximização da soma da diagonal»

Dada uma matriz quadrada de inteiros de tamanho N x N. Em um movimento, é possível deslocar ciclicamente qualquer linha para a esquerda ou para a direita por um número arbitrário de posições, ou deslocar ciclicamente qualquer coluna para cima ou para baixo por um número arbitrário de posições. O objetivo é maximizar a soma dos elementos na diagonal principal (do canto superior esquerdo ao canto inferior direito). Encontre a soma máxima possível após qualquer número dessas operações. N de 1 a 100, os elementos da matriz são números inteiros de -10^6 a 10^6.

Formato de Entrada

Na primeira linha, um número inteiro N. Em seguida, N linhas, cada uma contendo N números inteiros separados por espaço.

Formato de Saída

Um único número inteiro — a soma máxima na diagonal principal.

Exemplos

Exemplo 1

ENTRADA

5
1 -2 3 -1 2

SAÍDA

5

Exemplo 2

ENTRADA

SAÍDA

18

Exemplo 3

ENTRADA

2
3 4
1 2

SAÍDA

6

main.rs