Sprouts

Baku divided a large square plot of land into equal parts and made $N \times N$ small square fields. He planted $P$ seeds in each field. One week later, some seeds had sprouted and others had not. The figure below shows $6 \times 6$ fields with $3$ seeds planted in each. The top left field has 2 sprouts, and the bottom right field has 1 sprout.

Baku recently learned about the median. The median is the middle value when an odd number of given values is sorted. For example, if the five values are $0, 1, 2, 2, 3$, the median is $2$.

Baku wants to compare the median and the mean of the sprout counts. To test many cases, he compares the median and the mean over every block of $K \times K$ adjacent fields. This gives $(N-K+1) \times (N-K+1)$ comparisons for the $N \times N$ fields.

For the figure above, the table below shows the medians and means for each $3 \times 3$ block. The top left $3 \times 3$ block has sprout counts $2, 1, 0, 0, 1, 0, 2, 0, 1$, so its median is $1$ and its mean is $7/9$. The top right $3 \times 3$ block has median $0$ and mean $8/9$.

Median	Mean

Baku wants the maximum difference between the median and the mean. In the example above, the maximum occurs in the block marked in red in the figure below. There the median is $0$ and the mean is $1$, so the difference is $1$.

	Median	Mean	Difference

For convenience, Baku wants the maximum of the difference between the median and the mean multiplied by $K^2$. In the example above, the answer is $9$.

You must implement the following function. It is called exactly once.

int diff( int K, int[][] V ) ;

$V$ is an $N \times N$ array (vector). It gives the sprout count $V[0..N-1][0..N-1]$ for each field. Compute the difference between the median and the mean for each $K \times K$ block, multiply it by $K^2$, and return the maximum value.

• $1 \le N \le 2\,000$
• $K$ is odd and $1 \le K \le N$
• $0 \le V_{ij} \le 30$ ($0 \le i, j \le N-1$)