Problem G
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 512000/512000K (Java/Other)
Total Submission(s) : 90 Accepted Submission(s) : 44
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
有个小老鼠在校园里收藏了一些它最爱吃的奶酪。
校园可以看成一个长度为n的正方形网格，每个网格可以标记为（p,q），其中，0 <= p , q < n. 每个网格都有一个洞，里面储存了k（0<=k<=100）块奶酪。
现在，小老鼠准备享用这些美味啦。
开始的时候，他在(0,0)这个位置，每到一个地方，它都会吃光这个地方的奶酪，然后沿着水平或者垂直的方向到达另外一个地方。麻烦的是，有个很凶的猫总是在它的洞口附近，所以他每次最多移动K个位置，否则就会被这只猫吃掉。更糟糕的是，每在一个地方吃过奶酪，小老鼠都会变胖，所以，为了获得足够下一次逃跑的能量，它每次只能去比当前位置的奶酪更多的格子。
现在已知n和k，以及在每个网格的洞中小老鼠储存的奶酪的数量，请计算小老鼠在无法移动之前，一共最多能吃到多少块奶酪。
校园可以看成一个长度为n的正方形网格，每个网格可以标记为（p,q），其中，0 <= p , q < n. 每个网格都有一个洞，里面储存了k（0<=k<=100）块奶酪。
现在，小老鼠准备享用这些美味啦。
开始的时候，他在(0,0)这个位置，每到一个地方，它都会吃光这个地方的奶酪，然后沿着水平或者垂直的方向到达另外一个地方。麻烦的是，有个很凶的猫总是在它的洞口附近，所以他每次最多移动K个位置，否则就会被这只猫吃掉。更糟糕的是，每在一个地方吃过奶酪，小老鼠都会变胖，所以，为了获得足够下一次逃跑的能量，它每次只能去比当前位置的奶酪更多的格子。
现在已知n和k，以及在每个网格的洞中小老鼠储存的奶酪的数量，请计算小老鼠在无法移动之前，一共最多能吃到多少块奶酪。
Input
题目包含多组测试数据。
每组测试数据组成如下：
首先一行包含2个不超过100的正整数n和k;
接下来n行，每行包含n个数：
第一行n个数分别表示 (0,0) (0,1) ... (0,n-1)这些位置储存的奶酪数量；
第二行n个数分别表示(1,0), (1,1), ... (1,n-1)这些位置储存的奶酪数量；
以此类推。
输入数据以两个-1结束。
每组测试数据组成如下：
首先一行包含2个不超过100的正整数n和k;
接下来n行，每行包含n个数：
第一行n个数分别表示 (0,0) (0,1) ... (0,n-1)这些位置储存的奶酪数量；
第二行n个数分别表示(1,0), (1,1), ... (1,n-1)这些位置储存的奶酪数量；
以此类推。
输入数据以两个-1结束。
Output
请输出小老鼠最多 能够吃到的奶酪数量，每组数据输出一行。
Sample Input
3 1 1 2 5 10 11 6 12 12 7 -1 -1
Sample Output
37