E - Selecting Photo Spots Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は N \times N のマス目で表される観光エリアの中から、K \times K の正方形の区域を一つ選んで写真撮影ツアーを企画しようとしています。上から i 行目、左から j 列目のマスには景観スコア A_{i,j} が定められています。

ここで K \times K の区域とは、整数 r, c（1 \leq r \leq N-K+1, 1 \leq c \leq N-K+1）を選んだとき、上から r 行目〜 r+K-1 行目かつ左から c 列目〜 c+K-1 列目に含まれる K \times K 個のマス全体を指します。

ライバルのツアー会社を経営する青木君は、高橋君が選んだ区域を知った上で、その区域内からちょうど一つのマスを選び、そのマスの景観スコアを 0 に変更します（他のマスの景観スコアは変化しません）。青木君はこの操作を必ず行わなければならず、スコアが既に 0 のマスを選ぶこともできます。青木君は、操作後の区域内の景観スコアの合計を最小化するようにマスを選びます。

青木君の操作後における区域内の K \times K 個のマスの景観スコアの合計を 満足度 と呼びます。高橋君は青木君の妨害を考慮した上で、満足度が最大となるように区域を選びます。このときの満足度の最大値を求めてください。

制約

  • 1 \leq K \leq N \leq 1000
  • 0 \leq A_{i,j} \leq 10^9
  • 入力はすべて整数である。

入力

入力は以下の形式で与えられます。

N K
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
  • 1 行目には、エリアの一辺の大きさを表す整数 N と、選ぶ区域の一辺の大きさを表す整数 K が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には N 個の整数 A_{i,1}, A_{i,2}, \ldots, A_{i,N} がスペース区切りで与えられる。A_{i,j} は上から i 行目、左から j 列目のマスの景観スコアを表す。

出力

青木君が最適に妨害を行った場合における、高橋君が得られる満足度の最大値を整数で一行に出力してください。

入力例 1

3 2
1 2 3
4 5 6
7 8 9

出力例 1

19

入力例 2

4 4
0 2 5 1
4 0 3 6
7 8 0 2
1 9 4 0

出力例 2

43

入力例 3

5 3
8 1 6 2 9
3 5 7 4 1
9 2 4 8 3
6 0 5 7 2
1 8 3 9 4

出力例 3

37

入力例 4

8 4
12 7 3 15 8 6 14 2
9 11 5 4 13 10 1 16
6 14 2 12 7 15 3 8
10 1 16 9 5 11 4 13
8 13 7 3 14 2 12 6
4 15 10 1 16 9 5 11
14 2 12 6 8 13 7 3
5 11 4 16 10 1 15 9

出力例 4

132

入力例 5

1 1
1000000000

出力例 5

0

Score : 466 pts

Problem Statement

Takahashi is planning a photo tour by selecting a single K \times K square area from a sightseeing region represented as an N \times N grid. The cell in the i-th row from the top and the j-th column from the left has a scenery score of A_{i,j}.

Here, a K \times K area refers to the set of all K \times K cells from row r to row r+K-1 and from column c to column c+K-1, where integers r, c are chosen such that 1 \leq r \leq N-K+1 and 1 \leq c \leq N-K+1.

Aoki, who runs a rival tour company, learns which area Takahashi has chosen, and then selects exactly one cell within that area to change its scenery score to 0 (the scenery scores of all other cells remain unchanged). Aoki must perform this operation, and may choose a cell whose score is already 0. Aoki selects the cell so as to minimize the total scenery score within the area after the operation.

The total scenery score of the K \times K cells in the area after Aoki's operation is called the satisfaction. Takahashi, taking Aoki's sabotage into account, chooses the area to maximize the satisfaction. Find the maximum value of the satisfaction.

Constraints

  • 1 \leq K \leq N \leq 1000
  • 0 \leq A_{i,j} \leq 10^9
  • All input values are integers.

Input

The input is given in the following format:

N K
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
  • The first line contains two integers separated by a space: N, the side length of the area, and K, the side length of the chosen square.
  • Each of the following N lines, where the i-th line (1 \leq i \leq N), contains N integers A_{i,1}, A_{i,2}, \ldots, A_{i,N} separated by spaces. A_{i,j} represents the scenery score of the cell in the i-th row from the top and the j-th column from the left.

Output

Print, as a single integer on one line, the maximum satisfaction Takahashi can achieve when Aoki sabotages optimally.

Sample Input 1

3 2
1 2 3
4 5 6
7 8 9

Sample Output 1

19

Sample Input 2

4 4
0 2 5 1
4 0 3 6
7 8 0 2
1 9 4 0

Sample Output 2

43

Sample Input 3

5 3
8 1 6 2 9
3 5 7 4 1
9 2 4 8 3
6 0 5 7 2
1 8 3 9 4

Sample Output 3

37

Sample Input 4

8 4
12 7 3 15 8 6 14 2
9 11 5 4 13 10 1 16
6 14 2 12 7 15 3 8
10 1 16 9 5 11 4 13
8 13 7 3 14 2 12 6
4 15 10 1 16 9 5 11
14 2 12 6 8 13 7 3
5 11 4 16 10 1 15 9

Sample Output 4

132

Sample Input 5

1 1
1000000000

Sample Output 5

0