class Solution {
    fun abs(x: Int): Int = listOf(x, -x).max()

    private data class Accumulator(val sum: Long, val negatives: Int, val minimumAbs: Int) {
        fun update(x: Int): Accumulator =
            Accumulator(
                sum + abs(x),
                negatives +
                    if (x < 0) {
                        1
                    } else {
                        0
                    },
                listOf(minimumAbs, abs(x)).min(),
            )

        fun adjust(): Accumulator =
            when {
                negatives % 2 != 0 -> Accumulator(sum - 2 * minimumAbs, negatives, minimumAbs)
                else -> this
            }
    }

    fun maxMatrixSum(matrix: Array<IntArray>): Long =
        matrix.fold(Accumulator(0L, 0, Int.MAX_VALUE)) { acc, row ->
            row.fold(acc) { acc, it ->
                acc.update(it)
            }
        }.adjust().sum
}