OpenJudge

02:sophie打地鼠

总时间限制:
5000ms
单个测试点时间限制:
1000ms
内存限制:
65536kB
描述

sophie正在玩打地鼠游戏,游戏画面是一个N×N的点阵,每个点上的数字代表这个点的地鼠数量。

sophie有一个三角形的(奇葩)锤子,其形状为边长为K的直角三角形。

如图所示,若k=4,当sophie敲击绿色点,红色点会一并被敲击到,并且不能旋转锤子

请问,sophie使用这个锤子敲击时最多能打中多少地鼠。


输入
第1行包含2个正整数N,K
以下N行,每行N个整数,代表每个点上的地鼠数量。
输出
输出一个整数,代表最多能砸到的地鼠数。
样例输入
3 2
5 1 0
3 0 0
0 1 0
样例输出
8
提示
对于 40% 的测试数据,满足 1≤N≤300,1≤K≤10;
对于 80% 的测试数据,满足 1≤N≤1000,1≤K≤10;
对于 100% 的测试数据,满足 1≤N≤1000,1≤K≤50。

*请仔细估算复杂度,并尝试用预处理前缀和进行优化
*注意输入数据达到10^6数量级,需使用scanf
全局题号
15746
提交次数
23
尝试人数
15
通过人数
10