cho.sh
Notes
Loading...

Maximum Sum of a Two-Dimensional Array

Time limit

2s

Memory limit

128 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 82 5 3 5 2 06 8 1 5 0 34 8 2 6 9 29 1 6 5 3 27 0 2 4 3 1

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

6 0 8 2 6 92 5 3 5 2 06 8 1 5 0 34 8 2 6 9 29 1 6 5 3 27 0 2 4 3 1

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

5 0 8 2 6 91 5 3 5 2 05 8 1 5 0 33 8 2 6 9 28 1 6 5 3 26 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.

5 9 7 1 5 82 5 3 5 2 06 8 1 5 0 34 8 2 6 9 29 1 6 5 3 27 0 2 4 3 1
6 0 8 2 6 92 5 3 5 2 06 8 1 5 0 34 8 2 6 9 29 1 6 5 3 27 0 2 4 3 1
5 0 8 2 6 91 5 3 5 2 05 8 1 5 0 33 8 2 6 9 28 1 6 5 3 26 0 2 4 3 1