Target Sudoku Maximum Score

In Target Sudoku, you are given a 9x9 Sudoku grid with some cells pre-filled. In addition to the usual Sudoku rules -- each row, column, and 3x3 sub-grid must contain all digits 1 through 9 exactly once -- every cell has an associated score based on its distance from the center. Specifically, for a cell at row i and column j (0-indexed), let d = max(|i - 4|, |j - 4|). Then the cell's score is defined as follows:

• If d = 0, the score is 10.
• If d = 1, the score is 9.
• If d = 2, the score is 8.
• If d = 3, the score is 7.
• If d = 4, the score is 6.

The total score of a completed grid is the sum over all cells of (cell score × digit placed in that cell). Given a partially filled grid (with 0 representing an empty cell), determine the maximum possible total score that can be achieved by completing the board under standard Sudoku rules.

Note that some puzzles may have more than one valid completion; in that case, choose the one that maximizes the total score.

inputFormat

The input consists of 9 lines. Each line contains 9 integers separated by spaces, representing the Sudoku grid. A 0 represents an empty cell which must be filled with a digit from 1 to 9.

outputFormat

Output a single integer: the maximum total score achievable for the given Target Sudoku puzzle.

sample

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

2846