Flattening the Hills

You are given an \( n \times n \) matrix representing the heights of hills. Your task is to compute the minimum cost to make all hills the same height. The cost is defined as the sum of the absolute differences between each hill's height and a target height \( M \).

The optimal target height is the median of all hill heights because the median minimizes the sum of absolute deviations. Formally, if the heights are \( h_1, h_2, \dots, h_{n^2} \), then the minimum cost can be computed as:

\[ \text{cost} = \sum_{i=1}^{n^2} |h_i - M| \]

where \( M \) is the median of \( \{h_i\} \).

inputFormat

The first line contains an integer \( n \) indicating the size of the matrix \( (n \times n) \). Each of the next \( n \) lines contains \( n \) space-separated integers, representing the heights of the hills.

outputFormat

Output a single integer representing the minimum cost to make all hills the same height.

## sample

3
1 2 3
4 5 6
7 8 9

20