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