题目描述

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

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

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

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

---

输入格式

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

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

---

输出格式

一个整数：答案。

---

样例 1

输入

2
0
1 0

输出

1

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

---

样例 2

输入

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

输出

10

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

---

数据范围与提示

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

子任务	分值	数据范围
1	$10$ 分	$n\leq 5$
2		$n\leq 50$
3		$n\leq 200$
4	$20$ 分	$n\leq 1000$
5	$50$ 分	$n\leq 5000$

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

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