Minimum Sum Matrix Transformation

You are given an \( n \times n \) matrix. You are allowed to choose any submatrix and replace all its elements with the maximum element of that submatrix. This operation can be performed arbitrarily many times (including zero). Determine the minimum possible sum of the matrix after applying such operations.

Observation: Repeatedly applying the operation can make all elements in the matrix equal to the maximum element in the original matrix. Hence, the answer is given by:

[ \text{Answer} = n^2 \times \max(\text{matrix}) ]

Examples:

• For a 3x3 matrix with elements from 1 to 9, the answer is \(3^2 \times 9 = 81\).
• For a 2x2 matrix with all elements 5, the answer is \(2^2 \times 5 = 20\).

inputFormat

The first line contains a single integer \( n \) denoting the dimension of the \( n \times n \) matrix. Each of the following \( n \) lines contains \( n \) space-separated integers representing the matrix rows.

outputFormat

Output a single integer — the minimum possible sum of the matrix after performing the allowed operations.

3
1 2 3
4 5 6
7 8 9

81