Baku has divided a large square plot of land into $N \times N$ smaller square fields. After planting $P$ seeds in each field, he checked them a week later and found that some seeds had sprouted while others had not. For example, the image below shows the state of sprouts in a $6 \times 6$ grid after planting 3 seeds in each field. The top-left field has two sprouts, and the bottom-right field has one sprout.

Baku, while looking over the fields, remembered the median he recently learned about. The median is one of a given set of odd-numbered values, which is the value exactly in the middle when the given values are sorted. For example, if the five given values are 0, 1, 2, 2, 3, the median is 2.

Baku is curious about how much the median and the mean can differ, so he wants to compare the median and the mean of the number of sprouts in each field. To examine various cases, the median and mean to be compared are calculated for adjacent $K \times K$ square fields. This allows for a total of $(N - K + 1) \times (N - K + 1)$ comparisons in the given $N \times N$ fields.

For example, if we calculate both the median and the mean for the $3 \times 3$ units of the fields in the image above, we get the table below. The number of sprouts in the top-left $3 \times 3$ fields are 2, 1, 0, 0, 1, 0, 2, 0, 1, so the median is 1 and the mean is $7/9$. For the top-right $3 \times 3$ fields, the median is 0 and the mean is $8/9$.

Baku wants to find the maximum value of the difference between the median and the mean. In the example above, the case with the maximum value is the part marked with a red square in the image below, where the median is 0 and the mean is 1, so the difference between the two values is 1.

For convenience in calculation, Baku wants to find the maximum value of the difference between the median and the mean multiplied by $K^2$. Therefore, the maximum value in the example above is 9. You must implement the following function for Baku.

int diff( int K, int[][] V ) ; This function is called exactly once. $V$ is an $N \times N$ array (vector). The number of sprouts in each field $V[0..N-1][0..N-1]$ is given as an argument. Find and return the maximum value of the difference between the median and the mean calculated for $K \times K$ units, multiplied by $K^2$.

Implementation Details

You must submit a single file named sprout.cpp. This file must contain the implementation of the following function:

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

This function must operate as described above. Of course, you may create other functions and use them internally. The submitted code must not perform input/output or access other files.

Grader Example

The provided grader reads input in the following format:

• line 1: $N$ $K$ ($N$: size of the field, $K$: size of the region)
• line 2+$i$ ($0 \le i \le N-1$): $V_{i0}$ $V_{i1}$ $\dots$ $V_{iN-1}$ ($V_{i0}, V_{i1}, \dots, V_{iN-1}$: number of sprouts in row $i$)

The provided grader outputs the value returned by your code's diff() function.

Constraints

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

Subtasks

• Subtask 1 [17 points]: $N \le 100$
• Subtask 2 [24 points]: $N \le 300$
• Subtask 3 [42 points]: $N \le 700$
• Subtask 4 [67 points]: No additional constraints.

Examples

Input 1

6 3
2 1 0 1 0 2
0 1 0 3 0 0
2 0 1 0 0 2
1 2 2 2 2 0
1 2 2 0 0 1
0 1 0 0 2 1

Output 1

9

Input 2

4 3
10 20 10 20
20 10 20 10
10 20 10 20
20 10 20 10

Output 2

40

Figure 1. The state of sprouts in a 6x6 grid after planting 3 seeds in each field.