새싹 | cho.sh

바쿠는 정사각형 모양의 넓은 땅을 균등하게 구획을 나눠 작은 정사각형 밭을 $N \times N$ 개 만들 었다. 각 밭에 $P$ 개씩 씨를 뿌린 후 일주일 후에 보니 어떤 씨는 새싹이 났고 어떤 씨는 아직 새싹이 나지 않았다. 예를 들어, 아래 그림은 $6 \times 6$ 개의 밭에 $3$ 개씩의 씨를 뿌린 후 새싹이 난 모습을 나타낸다. 가장 왼쪽 위 밭에는 두 개의 새싹이 났고, 가장 오른쪽 아래 밭에는 한 개의 새싹이 났다.

밭을 둘러보던 바쿠는 최근에 배운 중간값(median)이 생각났다. 중간값은 홀수개의 주어진 값들 중 하나로, 주어진 값들을 정렬했을 때 정확히 가운데에 있는 값이다. 예를 들어, 다섯 개의 주어진 값이 $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 한다.

새싹

문제

제한