问题 23046 --挖宝藏

23046: 挖宝藏

时间限制: 1 Sec  内存限制: 128 MB
提交: 112  解决: 31
[提交][状态][讨论版][命题人:]

题目描述

某片矿区含有丰富的矿产资源,有金银铜铁锡等,还有钻石呢。很多人前去淘金。你现在手上有一笔资金,可买到该矿山面积为S平方米的地域进行开采,你通过秘密途径搞到一份绝密资料,那就是该矿山的资源分布图。有了这些资料后,你准备买下哪块地进行开采,才能得到最大的效益。

输入

第一行为一个整数NN<=100),表示矿山的边长。接下来是矿山的资源分布图,按单位平方米标记了每个点开采的价值,若为负数,表示开采将会亏本。最后一行为一个整数S,表示你可开采的面积(S<10000

输出

输出开采后你的最大收益,注意你最大可以买S,你也可以买小于S的面积。为了规划,买的地域必须成矩型。

样例输入

3
1 2 3
-1 2 4
-3 -2 3
4

样例输出

11

来源

 

[提交][状态]