北欧大学生乒乓球锦标赛（NCPC）是一项竞争极其激烈的赛事，每位参赛者都要与其他所有参赛者进行且仅进行一场乒乓球比赛。锦标赛的最后一场比赛刚刚结束，现在议程上只剩下一项内容：传统的颁奖典礼，所有参赛者都将入选 NCPC 名人堂。

根据古老的习俗，尚未入选名人堂的参赛者（“无名小卒”）必须留在舞台左侧，而已经入选的参赛者（“传奇大神”）则必须站在舞台右侧。当一名参赛者领取证书时，他们会象征性地从舞台左侧走到右侧，从而成为一名“传奇大神”。名人堂一次只接纳一名参赛者，且所有参赛者最初都站在左侧。

NCPC 裁判长认为，如果右侧的“传奇大神”中有太多人曾经输给过左侧的“无名小卒”，这会让她显得很没面子。但她很快意识到，在颁奖典礼的整个过程中，完全避免这种情况可能是不可能的。不过，她确实希望将这种“惨剧”降到最低。具体来说，她希望找到一个最小的整数 $k$，使得存在一种颁发证书的顺序，在任何时刻，右侧的“传奇大神”输给左侧的“无名小卒”的比赛场次都不会超过 $k$ 场。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5\,000$)，表示参赛者人数。 接下来有 $n-1$ 行，其中第 $i$ 行包含一个长度为 $i$ 的二进制字符串。第 $i$ 行的第 $j$ 个字符如果为 $1$，表示参赛者 $i+1$ 击败了参赛者 $j$；如果为 $0$，则表示参赛者 $j$ 击败了参赛者 $i+1$。

输出格式

输出一个整数 $k$，即满足上述要求的最小数值。

样例

样例输入 1

4
1
01
100

样例输出 1

1

样例输入 2

5
0
00
100
1100

样例输出 2

3