Problem F
Incremental Induction
According to the ancient customs, contestants who have not been inducted into the Hall of Fame yet (the pathetic nobodies) must stay on the left side of the stage, whereas contestants who have been inducted (the awesome legends) must be on the right side of the stage. Then, when a contestant is receiving their diploma, they will symbolically walk from the left to the right side of the stage and thus become an awesome legend. Only one contestant is inducted into the Hall of Fame at a time, and every contestant starts on the left side initially.
The NCPC Head of Jury believes it reflects badly on her if too many of the awesome legends on the right have lost matches against pathetic nobodies on the left, but she quickly realizes that it might be impossible to avoid this at every point in time during the diploma ceremony. However, she certainly wants to keep such atrocities at a minimum. Specifically, she wants to find the smallest number $k$ for which there exists an order of handing out diplomas to the contestants, such that at no point there were more than $k$ games played where an awesome legend lost against a pathetic nobody.
Input
The first line of input contains a single integer $n$ ($1 \leq n \leq 5\, 000$), the number of contestants. Then follows $n-1$ lines, the $i^{\text {th}}$ of which contains a binary string of length $i$. The $j^{\text {th}}$ character on the $i^{\text {th}}$ line is $1$ if contestant $i+1$ defeated contestant $j$, and $0$ if contestant $j$ defeated contestant $i+1$.
Output
Output a single integer $k$, the smallest number according to the requirements above.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 01 100 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 0 00 100 1100 |
3 |
