#P2213. [USACO14MAR] The Lazy Cow S

    ID: 1191 Type: RemoteJudge 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: 3 Uploaded By: Tags>图论2014USACO生成树前缀和

[USACO14MAR] The Lazy Cow S

题目描述

奶牛贝茜非常懒惰,她希望在她的地盘内找到一点最佳位置居住,以便在有限的步数内可以吃到尽量多的青草。

她的地盘是一个 N×N(1N400)N \times N(1\le N \le 400) 的矩阵,第 rrcc 列包含 G(r,c)G(r,c) 单位的青草 (0G(r,c)1000)(0 \le G(r,c) \le 1000)。从她的居住点,她最多愿意走 KK(0K2×N)(0 \le K \le 2 \times N),每一步她可以走到上与她相邻的某个格子。

输入格式

第一行两个正整数 N,KN,K

输出格式

一行一个整数,表示奶牛贝茜在有限的步数内最多可以吃到多少青草。

5 2
50 5 25 6 17
14 3 2 7 21
99 10 1 2 80
8 7 5 23 11
10 0 78 1 9

342

提示

样例解释:

最优方案是居住在 (3,3)(3,3),答案为 342342

50    5     25*   6     17    
14    3*    2*    7*    21    
99*   10*   1*(B) 2*    80*    
8     7*    5*    23*   11   
10    0     78*   1     9