We define a magic square to be an matrix of distinct positive integers from to where the sum of any row, column, or diagonal of length is always equal to the same number: the magic constant.
You will be given a matrix of integers in the inclusive range . We can convert any digit to any other digit in the range at cost of . Given , convert it into a magic square at minimal cost. Print this cost on a new line.
Note: The resulting magic square must contain distinct integers in the inclusive range .
For example, we start with the following matrix :
We can convert it to the following magic square:
This took three replacements at a cost of .
Each of the lines contains three space-separated integers of row .
Print an integer denoting the minimum cost of turning matrix into a magic square.
Sample Input 0
4 9 23 5 78 1 5
Sample Output 0
If we change the bottom right value, , from to at a cost of , becomes a magic square at the minimum possible cost.