题目描述

3206年5月，正在钻研ET专业的刘博士所在的OI团队发现：地球受到了来自外星球的生物人的侵袭。这些生物人采取了极秘的乘法加密电文，控制了具有大量武器的军火库，攻占了大量的城市，甚至出现了K弹计划……

刘博士所在的OI团队决定要发挥他们的科研机构作用（由于吉林省所在的地理位置具有特殊的优势，此科研机构全球只有吉林一处），以制伏这些外星球的生物人。他们想方设法捕获了几个外星球的生物人，经研究后发现，这些外星球的生物人在地球上的生存，取决于一个参数：生存度。他们要做的就是：找到这个参数的最大值！于是，他们开始了对这些外星球的生物人生长的研究。

每次实验前，他们把一个外星球生物人的细胞随机地放在一个N*N的方形培养容器的一格中，并给容器的每个格子都标了一个数值，是生物在此单元的生存度（可正可负，数值越大表示越危险）。整个生物的生存度是生物所有占据格子的生存度之和。每次实验开始后，让生物自然生长。这个生物每一单位时间都选择其身体的一部分（某个格子），随机地向与之有公共边的空格生长，例如某次实验，一开始生物只占据一个格子，然后开始了生长：

刘博士所在的OI团队做了大量的实验，并且对数据进行了记录和统计。假设进行的实验次数足够多，问在实验进行的某一时刻，该生物达到的最大生存度是多少？

3206年9月，妄图破坏地球的外星球生物人终于被刘博士所在的OI团队制伏了……

输入格式

输入文件第一行包括一个正整数N，代表实验容器的边长。

接下来N行，每行N个用空格隔开的整数，代表外星球生物人在每一格的生存度。

输出格式

输出一行，代表实验过程中，生物达到的最大生存度。

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

18

提示

对于40%的数据有N <= 6。

对于100%的数据有N <= 9。

所有数据每个格子生存度的绝对值不超过32767。