Циклический сдвиг матрицы с максимизацией суммы диагонали

Rust Сложный loops

Задача «Циклический сдвиг матрицы с максимизацией суммы диагонали»

Дана квадратная матрица целых чисел размера N x N. За один ход можно циклически сдвинуть любую строку влево или вправо на произвольное количество позиций, либо циклически сдвинуть любой столбец вверх или вниз на произвольное количество позиций. Цель — максимизировать сумму элементов на главной диагонали (от верхнего левого угла до нижнего правого). Найдите максимально возможную сумму после любого количества таких операций. N от 1 до 100, элементы матрицы — целые числа от -10^6 до 10^6.

Формат ввода

В первой строке целое число N. Далее N строк, каждая содержит N целых чисел через пробел.

Формат вывода

Одно целое число — максимальная сумма на главной диагонали.

Примеры

Пример 1

ВВОД

5
1 -2 3 -1 2

ВЫВОД

5

Пример 2

ВВОД

ВЫВОД

18

Пример 3

ВВОД

2
3 4
1 2

ВЫВОД

6

main.rs