问题 M: 挖宝藏
传统题
1.000s
时间限制
128MB
内存限制
3 提交
2 解决
【题目描述】
某片矿区含有丰富的矿产资源，有金银铜铁锡等，还有钻石呢。很多人前去淘金。
你现在手上有一笔资金，可买到该矿山面积为S平方米的地域进行开采，你通过秘密途径搞到一份绝密资料，那就是该矿山的资源分布图。
有了这些资料后，你准备买下哪块地进行开采，才能得到最大的效益。
【输入】
第一行为一个整数
N（
N<=100），表示矿山的边长。
接下来是矿山的资源分布图，按单位平方米标记了每个点开采的价值，若为负数，表示开采将会亏本。
最后一行为一个整数
S，表示你可开采的面积（
S<10000）
【输出】
输出开采后你的最大收益，注意你最大可以买S，你也可以买小于S的面积。为了规划，买的地域必须成矩型。
【样例输入】复制
3
1 2 3
-1 2 4
-3 -2 3
4