题目背景及题目

9999年，chr在某个地方发现了一个能量阵。这个能量阵由能量水晶组成，这些魔法水晶呈三角形状排布，一共有\(n\)行，第\(i\)行有\(i\)个，这些魔法水晶都储存了巨大的能量，可惜有一些魔法水晶被破坏了。
10000年，外星人入侵地球。xdh，作为地球军团的总司令，必须消灭这些外星人。他决定激活这个能量阵。他可以激活一些能量水晶，要求这些能量水晶构成一个三角形（不能有突出来的部分，中间是空的）。这些能量水晶会修复内部的能量水晶并激活内部的能量水晶。最终这个小能量阵的威力就是被激发的能量水晶数目。为了让威力最大化，三角形必须是正着放的。
因为他派你要保卫地球，所以你必须选择威力最大的小能量阵。
请你计算小能量阵的威力的最大值。如果不能选择任何能量水晶就输出 0 。

输入输出格式

输入

第一行有一个整数\(n\)。
接下来，有\(n\)行，第\(i\)行有\(i\)个整数，第\(j\)个数\(a_i,_j\)表示第\(j\)个魔法水晶的状态，\(1\)表示已损坏，\(0\)表示未损坏。

输出

一个整数，为答案

样例

Input1

2
0
1 0

Output1

1

input2

5
0
0 0
0 0 1
0 1 0 0
0 0 0 0 1

Output2

10

数据范围说明

本题输入量较大，建议使用较快的输入方法
对于百分之百的数据，\(1 \leq n \leq 5000\),\(a_i,_j \in {0,1}\).

评测时空分配（每单个数据）

时间

1s

空间

足够，最大300MB