#  https://leetcode.com/problems/maximum-matrix-sum
from typing import List

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        total = 0
        negative_count = 0
        min_val = float("inf")
        length = len(matrix)
        for i in range(length):
            for j in range(length):
                if matrix[i][j] < 0:
                    total += -matrix[i][j]
                    negative_count += 1
                else:
                    total += matrix[i][j]
                min_val = min(min_val, abs(matrix[i][j]))
        if negative_count % 2 != 0:
            total -= 2 * int(min_val)
        return total