你是当地动物园的一名员工，最近刚从排泄物清理岗位晋升为负责全园人行道布局的规划员。目前，所有的步道都是单向的，动物园被划分为若干个“区域”（zones）。每个区域由一组景点（如大象馆、蜥蜴馆等）组成，在同一个区域内，你可以通过一条或多条步道从任意一个景点到达该区域内的任何其他景点。一旦你从一个区域走到另一个区域，就无法再回到离开的那个区域。不过，在一次游园过程中，可以走遍所有的区域。最初的设计者认为这种安排对于控制游客在动物园内的流动非常重要。

董事会成员向你提出了一个问题。他们认同最初设计者关于区域划分的理念，但他们觉得可以增加更多的单向步道，使动物园对游客更友好。他们希望你计算出在不引入任何之前不存在路径的两个景点之间的新路径的前提下，最多可以增加多少条步道。

例如，考虑图 J.1 中所示的小型动物园，共有 7 个景点，编号从 1（“骆驼城堡”）到 7（“河马竞技场”）。目前，景点 1、2、3 和 4 构成一个区域，5、6 和 7 构成另一个区域。你可以增加从 1、2、3 或 4 到 5、6 或 7 的步道，但增加一条从（例如）7 到 1 的步道将允许游客从 7 到达 1，而这在之前是不可能的。注意，你也可以在区域内所有尚未存在步道的景点之间增加步道（例如，从 1 到 3 或从 2 到 4）。对于这个动物园，可能增加的新步道总数为 21。

图 J.1：示例动物园。此示例对应样例输入 1。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 2500$)，表示景点的数量，编号为 1 到 $n$。 接下来有 $n$ 行，每行包含 $n$ 个整数。如果第 $i$ 行的第 $j$ 个整数为 1，则表示存在一条从景点 $i$ 到景点 $j$ 的单向步道；否则该整数为 0，表示不存在此类步道。景点到自身永远不会有步道。

输出格式

输出可以增加到动物园中的最大新单向步道数量。

样例

样例输入 1

7
0 1 0 0 0 0 0
0 0 1 0 1 0 0
1 0 0 1 0 0 0
1 0 0 0 0 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 1
0 0 0 0 1 0 0

样例输出 1

21

样例输入 2

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

样例输出 2

6

样例输入 3

2
0 1
1 0

样例输出 3

0