Problem 23046 --挖宝藏

23046: 挖宝藏

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 112  Solved: 31
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][120kb]

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

11

HINT

Source

[Submit][Status]