printЗадачи очного тура личного первенства

print6. Игра

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Макси и Мини играют в следующую игру. Квадратный лист бумаги разделяется линиями на `N\ times\ N` клеток, и в каждой клетке записывается целое число от –100 до 100. Игроки ходят по очереди. Каждый игрок может либо взять себе весь оставшийся прямоугольник, либо разрезать его по вертикальной или горизонтальной линии на два прямоугольника и взять себе любую из частей. Игра заканчивается, когда игрок при очередном ходе забирает себе всю оставшуюся фигуру. По окончании игры подсчитывается сумма чисел на взятых игроками частях. Побеждает тот игрок, у которого сумма больше.
Напишите программу, которая по значениям в клетках в начале игры определит максимальный перевес первого игрока над вторым, если оба играют максимально прибыльно для себя.
В первой строке входного файла содежится число `T` (`0\ <\ T\ ≤\ 10`) – количество тестов в файле. Каждый тест состоит из набора строк. В первой строке содержится целое число `N` (`0\ <\ N\ ≤\ 10`) – размер поля, затем следует `N` строк, в каждой содержится `N` целых чисел `A_{ij}` (`-100\ ≤\ A_{ij}\ ≤\ 100`), разделенных пробелами – числа, записанные в соответствующих клетках.
Для каждого теста вывести на соответствующей строке максимальный перевес первого игрока над вторым по окончании игры, если оба играют максимально прибыльно для себя.

Пример ввода

2
3
1 1 1
1 1 1
1 1 1
2
-10 1
1 1

Пример вывода

9
-7
loading