새싹

바쿠는 넓은 정사각형 땅을 똑같이 나누어 작은 정사각형 밭 $N \times N$개를 만들었다. 각 밭에 씨를 $P$개씩 뿌린 뒤 일주일 후에 확인하니, 새싹이 난 씨도 있고 아직 나지 않은 씨도 있었다. 아래 그림은 $6 \times 6$개의 밭에 씨를 $3$개씩 뿌린 후의 모습이다. 가장 왼쪽 위 밭에는 새싹이 2개 났고, 가장 오른쪽 아래 밭에는 1개 났다.

바쿠는 최근 중간값을 배웠다. 중간값은 홀수 개의 주어진 값을 정렬했을 때 정확히 가운데에 있는 값이다. 예를 들어 다섯 개의 값이 $0, 1, 2, 2, 3$이라면 중간값은 $2$이다.

바쿠는 밭마다 난 새싹 개수의 중간값과 평균을 비교하려 한다. 다양한 경우를 보기 위해, 정사각형 모양으로 인접한 $K \times K$개 밭 단위로 중간값과 평균을 구한다. 이렇게 하면 $N \times N$개 밭에서 총 $(N-K+1) \times (N-K+1)$번 비교할 수 있다.

위 그림의 밭에 대해 $3 \times 3$개 단위로 중간값과 평균을 구하면 아래 표와 같다. 가장 왼쪽 위의 $3 \times 3$개 밭에 난 새싹 개수는 $2, 1, 0, 0, 1, 0, 2, 0, 1$이므로 중간값은 $1$, 평균은 $7/9$이다. 가장 오른쪽 위의 $3 \times 3$개 밭은 중간값이 $0$, 평균이 $8/9$이다.

중간값	평균

바쿠는 중간값과 평균의 차이가 가장 큰 경우를 찾으려 한다. 위 예에서 최댓값은 아래 그림에서 붉은 정사각형으로 표시한 부분이다. 이 부분은 중간값이 $0$, 평균이 $1$이므로 차이는 $1$이다.

	중간값	평균	차이

계산을 편하게 하려고 바쿠는 중간값과 평균의 차이에 $K^2$를 곱한 값의 최댓값을 구하려 한다. 따라서 위 예에서 최댓값은 $9$이다.

다음 함수를 구현해야 한다. 이 함수는 단 한 번 호출된다.

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

$V$는 크기가 $N \times N$인 배열(vector)이다. 각 밭에 난 새싹 개수 $V[0..N-1][0..N-1]$이 인자로 주어진다. $K \times K$ 크기 단위로 구한 중간값과 평균의 차이를 $K^2$배 한 값의 최댓값을 구하여 return 한다.

• $1 \le N \le 2\,000$
• $K$는 홀수이며 $1 \le K \le N$
• $0 \le V_{ij} \le 30$ ($0 \le i, j \le N-1$)