题目描述

2100年，yww在地球的某个角落发现了一个魔法阵。这个魔法阵包含很多魔法水晶，这些魔法水晶呈三角形状排布，一共有 $n$ 行，第 $i$ 行有 $i$ 个。这些魔法水晶都储存了巨大的能量，可惜有一些魔法水晶被破坏了。

2200年，外星人入侵地球。你，作为地球军团的总司令，必须消灭这些外星人。你决定激活这个魔法阵。你可以激活一些魔法水晶，要求这些魔法水晶构成一个三角形（不能有突出来的部分，中间是空的）。这些魔法水晶会修复内部的魔法水晶并激活内部的魔法水晶。最终这个小魔法阵的威力就是被激发的魔法水晶数目。为了让威力最大化，三角形必须是正着放的。

因为你要保卫地球，所以你必须选择威力最大的小魔法阵。

请你计算小魔法阵的威力的最大值。如果不能选择任何魔法水晶就输出 $0$ 。

输入格式

第一行有一个整数 $n$ 。

接下来 $n$ 行，第 $i$ 行有 $i$ 个整数，第 $j$ 个数 $a_{i,j}$ 表示三角形第 $i$ 行第 $j$ 个魔法水晶的状态， $1$ 表示已损坏， $0$ 表示未损坏。

输出格式

一个整数：答案。

样例

样例一

input

2
0
1 0

output

1

explanation

随便选择一个未损坏的魔法水晶即可。

样例二

input

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

output

10

explanation

选 $(2,1),(3,1),(3,2),(4,1),(4,3),(5,1),(5,2),(5,3),(5,4)$ 即可。

数据范围与提示

本题输入量较大，建议使用快速的读入方式。

子任务 $1$（$10$ 分）：$n\leq 5$。

子任务 $2$（$10$ 分）：$n\leq 50$。

子任务 $3$（$10$ 分）：$n\leq 200$。

子任务 $4$（$20$ 分）：$n\leq 1000$。

~~子任务 $4.5$（$20$ 分）：$n\leq 5000$，数据随机，每个水晶有 $50\%$ 的概率未损坏， $50\%$ 的概率已损坏。~~由于数据太大，这个子任务被删除了。

子任务 $5$（$50$ 分）：$n\leq 5000$。

对于 $100\%$ 的数据，$1\leq n\leq 5000,a_{i,j}\in\{0,1\}$。

题目来源：全是水题的GDOI模拟赛 by yww