[JLOI2009] 神秘的生物
题目描述
3206年5月,正在钻研ET专业的刘博士所在的OI团队发现:地球受到了来自外星球的生物人的侵袭。这些生物人采取了极秘的乘法加密电文,控制了具有大量武器的军火库,攻占了大量的城市,甚至出现了K弹计划……
刘博士所在的OI团队决定要发挥他们的科研机构作用(由于吉林省所在的地理位置具有特殊的优势,此科研机构全球只有吉林一处),以制伏这些外星球的生物人。他们想方设法捕获了几个外星球的生物人,经研究后发现,这些外星球的生物人在地球上的生存,取决于一个参数:生存度。他们要做的就是:找到这个参数的最大值!于是,他们开始了对这些外星球的生物人生长的研究。
每次实验前,他们把一个外星球生物人的细胞随机地放在一个N\*N的方形培养容器的一格中,并给容器的每个格子都标了一个数值,是生物在此单元的生存度(可正可负,数值越大表示越危险)。整个生物的生存度是生物所有占据格子的生存度之和。每次实验开始后,让生物自然生长。这个生物每一单位时间都选择其身体的一部分(某个格子),随机地向与之有公共边的空格生长,例如某次实验,一开始生物只占据一个格子,然后开始了生长:
![](https://cdn.luogu.com.cn/upload/pic/6844.png)
刘博士所在的OI团队做了大量的实验,并且对数据进行了记录和统计。假设进行的实验次数足够多,问在实验进行的某一时刻,该生物达到的最大生存度是多少?
3206年9月,妄图破坏地球的外星球生物人终于被刘博士所在的OI团队制伏了……
输入输出格式
输入格式
输入文件第一行包括一个正整数N,代表实验容器的边长。
接下来N行,每行N个用空格隔开的整数,代表外星球生物人在每一格的生存度。
输出格式
输出一行,代表实验过程中,生物达到的最大生存度。
输入输出样例
输入样例 #1
4
2 -1 -1 -1
5 -5 -1 -5
3 2 -1 3
2 -2 -3 2
输出样例 #1
18
说明
对于40%的数据有N <= 6。
对于100%的数据有N <= 9。
所有数据每个格子生存度的绝对值不超过32767。