Phoenix and Dalgu

Phoenix and Dalgu play a game on an $N \times N$ grid. Cell $(i, j)$ has weight $A_{i,j}$. The game goes as follows.

• Dalgu picks one $K \times K$ square region and gives all cells in it to Yooni. However, the chosen region must not contain cell $(1, 1)$ or cell $(N, N)$.
• Phoenix starts at cell $(1, 1)$ and moves until reaching cell $(N, N)$. From cell $(r, c)$, Phoenix can move to $(r+1, c)$ or $(r, c+1)$. Phoenix cannot move outside the grid or onto cells given to Yooni.
• Phoenix's score is the sum of the weights of the cells Phoenix passes through.

Phoenix wants the score to be as large as possible, and Dalgu chooses the region to make it as small as possible. Assuming both play optimally, find the maximum score Phoenix can obtain.

The first line contains two integers $N$ and $K$, separated by a space. ($2 \le N \le 2000$; $1 \le K < N$)

Each of the next $N$ lines contains $N$ integers $A_{i,1}, A_{i,2}, \cdots, A_{i,N}$, separated by spaces. ($0 \le A_{i,j} \le 10000$)

Print the maximum score Phoenix can obtain.