Fast Fingers Thomas has just finished conducting a tryout for a poutine-eating contest, and needs to produce a ranklist. However,
the scoreboard has crashed and the rankings are lost! Individual beat individual
if individual
ate more poutine
than individual
. He vaguely remembers that some individuals ate more poutine than other individuals, but might not have enough data to fully
reconstruct the ranklist. He does remember that there were no ties in the contest.
He decides to email all the participants with a list of pairs of individuals, and expects to get a response with, for each pair, which individual did better.
Compute the minimum possible size of the list such that, independent of what responses he gets back with regards to which individual ate more poutine, he is guaranteed to be able to construct a correct full ranklist.
Constraints
There exists some ranklist consistent with the input.
Input Specification
The first line contains a single positive integer, .
The next lines contain a binary string of length
. If the
th character of the
th line is
1
, then individual
definitely did better than individual
. Otherwise, the
th character of the
th line is
0
.
Output Specification
Output the minimum number of pairs needed to always ascertain the ranklist.
Sample Input
3
011
000
000
Sample Output
1
Comments