Maximum Sum of a Two-Dimensional Array

Time limit2sMemory limit128 MB

Problem

A 6×6 array contains digits from 0 to 9. You may apply the operations below any number of times, and you want to maximize the sum of all values in the array.

  1. Choose an integer i from 1 to 6 and add 1 to all six values in row i.
  2. Choose an integer i from 1 to 6 and subtract 1 from all six values in row i.
  3. Choose an integer i from 1 to 6 and add 1 to all six values in column i.
  4. Choose an integer i from 1 to 6 and subtract 1 from all six values in column i.
  5. Add 1 to all six values on the diagonal from the upper left to the lower right.
  6. Add 1 to all six values on the diagonal from the upper right to the lower left.
  7. Subtract 1 from all six values on the diagonal from the upper left to the lower right.
  8. Subtract 1 from all six values on the diagonal from the upper right to the lower left.

Each operation may be used without limit. Values always remain single digits: adding 1 to 9 gives 0, and subtracting 1 from 0 gives 9.

Consider the following array.

5 9 7 1 5 8
2 5 3 5 2 0
6 8 1 5 0 3
4 8 2 6 9 2
9 1 6 5 3 2
7 0 2 4 3 1

If 1 is added to the first row, the array becomes:

6 0 8 2 6 9
2 5 3 5 2 0
6 8 1 5 0 3
4 8 2 6 9 2
9 1 6 5 3 2
7 0 2 4 3 1

From there, if 1 is subtracted from the first column, the array becomes:

5 0 8 2 6 9
1 5 3 5 2 0
5 8 1 5 0 3
3 8 2 6 9 2
8 1 6 5 3 2
6 0 2 4 3 1

Input

The array is given as 6 lines, each containing 6 integers. Every integer is between 0 and 9, inclusive.

Output

Print the maximum possible sum of all array values on the first line.