Farming

Time limit: 1 second
Memory limit: 256 megabytes

There is a farm in the shape of an \(N \cdot N\) grid. The cell \((i, j)\) has crops of value \(G_{i,j}\). If \(G_{i,j}\) is negative then the crops are rotten.

Abdulaziz and Almothana want to harvest \(K \cdot K\) sub-grids of crops each. Obviously, the sub-grids may not intersect. Can you help Abdulaziz and Almothana select them optimally so that the total sum of values for the sub-grids is maximized.

Note 1: A sub-grid is a sub-rectangle of the main grid.

Note 2: Two \(K \cdot K\) sub-grids will be selected such that they don’t interset.

Input

The first line contains \(N\) and \(K\). \((1 \leq 2*K \leq N \leq 500)\)

The next \(N\) lines contain \(N\) numbers each, the values of the crops. \((-10^9 \leq G_{i, j} \leq 10^9)\)

Output

Print the maximum total sum of the sub-grids.

Scoring

Group Constraints Points
\(1\) \(N = 2\) \(25\)
\(2\) All values of \(G_{i,j}\) are equal \(25\)
\(3\) \(N = 10\) \(25\)
\(4\) — \(25\)

Examples

Input

2 1
3 1
2 4

Output

7

Input

5 2
1 2 3 4 5
5 4 2 1 3
2 3 1 4 5
4 1 5 2 3
3 5 4 1 2

Output

29
Solution

Compute every \(K\times K\) sub-grid sum using two-dimensional prefix sums.

Two non-intersecting rectangles must be separated either horizontally or vertically. For every possible top-left row, store the best sub-grid starting on that row. Prefix and suffix maxima then give the best pair whose row intervals do not overlap. Repeat the same process for columns.

The complexity is \(O(N^2)\) time and memory.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
        int n, k;
        cin >> n >> k;

        vector<vector<long long>> prefix(n + 1, vector<long long>(n + 1));

        for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                        long long x;
                        cin >> x;
                        prefix[i][j] = x + prefix[i - 1][j] + prefix[i][j - 1]
                                                        - prefix[i - 1][j - 1];
                }
        }

        int m = n - k + 1;
        const long long NEG = -(1LL << 62);
        vector<long long> rowBest(m, NEG), colBest(m, NEG);

        for (int i = 0; i < m; i++) {
                for (int j = 0; j < m; j++) {
                        int bottom = i + k;
                        int right = j + k;
                        long long sum = prefix[bottom][right] - prefix[i][right]
                                                    - prefix[bottom][j] + prefix[i][j];
                        rowBest[i] = max(rowBest[i], sum);
                        colBest[j] = max(colBest[j], sum);
                }
        }

        auto bestSeparated = [&](const vector<long long>& best) {
                vector<long long> pref(m), suff(m);
                pref[0] = best[0];
                for (int i = 1; i < m; i++) {
                        pref[i] = max(pref[i - 1], best[i]);
                }

                suff[m - 1] = best[m - 1];
                for (int i = m - 2; i >= 0; i--) {
                        suff[i] = max(suff[i + 1], best[i]);
                }

                long long answer = NEG;
                for (int i = 0; i + k < m; i++) {
                        answer = max(answer, pref[i] + suff[i + k]);
                }
                return answer;
        };

        cout << max(bestSeparated(rowBest), bestSeparated(colBest)) << '\n';
}