说明

到暑假了，任老师不忍心看大家每天都盯着电脑屏幕，决定带acm队员去一个正n边形的操场P上跑操。

操场P上有很多很多条双向路径以供选择，其中每条路径都是连接了P中两个不同顶点的直线段。跑操时，任老师为每一名队员都安排了一条路径，让每一名队员都在一条固定的路径上跑来跑去。任老师不希望看到有同学撞到一起，所以安排的所有路径都不相交。（只要两路径有公共点就视为相交，包括同顶点的情况）

现在，给你一个已经存在了若干路径的正n边形操场P，请你帮任老师计算一下，在这个操场上最多可以安排多少名队员安全地跑操。

输入格式

第一行包含n(3<=n<=500)个整数，表示操场P的顶点个数。

第二行到第n + 1行每行包含n个整数，第i行第j个整数表示第i个顶点和第j个顶点间的状态，1表示有路径，0表示无路径。给出的数据保证每条路径都是双向，且保证第i行第i列的数字皆为0。

输出格式

输出可安排学生的最多人数。

样例

3
0 1 1
1 0 1
1 1 0

1

样例

6
0 0 0 1 0 0
0 0 0 0 1 1
0 0 0 0 1 1
1 0 0 0 0 0
0 1 1 0 0 0
0 1 1 0 0 0

2

提示

下面两图是两个样例。黑色实线和红色粗线表示可选择的路径，黑色虚线表示不可选择的边。

对于第一张图，我们最多只能选择一条边。因此答案是1。

对于第二张图，我们最多只能选择两条边（2，4）和（1，5）。因此答案是2。