Flip, найти максимальную сумму матрицы путем умножения линий и столбиков на Опции

[DarkWishmaster]

Привет. Вот интересная задача:
Дана матрица NxM где её элементы положитнльные и отрицательные числа. Можно умножить сколько раз угодно любую линию и любой столбик на -1. Найдите максимальную суму чисел из матрицы которая может получиться путем этих умножений.
Например:
5 3
4 -2 2
3 -1 5
2 0 -3
4 1 -3
5 -3 2
Умножаем 3 линию и 2 столбик. Сума=28.
Есть идеи как это вообще сделать?
Сначала я думал что можно пройтись по линиям и столбикам и если по модулю сума отрицательных чисел больше положительных то умножаем на -1, но такой способ не помогает так как когда мы умножаем линию то изменются и колоны и наоборот.

[Lapp]

DarkWishmaster, ограничения на размеры матрицы накладываются?

[DarkWishmaster]

DarkWishmaster, ограничения на размеры матрицы накладываются?

Да, извините, совсем забыл: 1<=N,M<=18,

Добавлено через 15 мин.

Да, извините, совсем забыл: 1<=N,M<=18,

IUnknown, Обьясните пожалуйста вот эту строку:

        minusi := 1 - 2 * ((rows shr i) and $1);
        minusj := 1 - 2 * ((cols shr j) and $1);
 

Ещё это $1. Я так понял если (rows shr i) четно то выдает 0 иначе 1.