Bored Dreamoon

Dreamoon serves in the military this year. Everything in the military is boring. To make military life more interesting, Dreamoon decided to turn some of his military experiences into programming competition problems.

Leaders usually order soldiers to stand in several rows ordered by their heights. The arrangement rules are as follows:

• If two soldiers $A$ and $B$ stand in different rows, and $A$'s row is in front of $B$'s row, then $A$ is shorter than $B$.
• If two soldiers $A$ and $B$ stand in the same row, and $A$ is to the right of $B$, then $A$ is shorter than $B$.
• For any two rows, the difference between the number of soldiers in them is at most $1$.
• For any two rows, the number of soldiers in the front row is equal to or larger than the number of soldiers in the back row.

After Dreamoon noticed these properties, the following problem came to his mind.

For two different soldiers $A$ and $B$, we say $B$ is right front of $A$ if $A$'s row is NOT in front of $B$'s row, and the number of soldiers to the right of $B$ in $B$'s row is not larger than the number of soldiers to the right of $A$ in $A$'s row.

You do not know how many soldiers there are in total, and you do not know how many rows they are arranged into. You do know the heights of $N$ soldiers, numbered from $1$ through $N$. For any two distinct numbers $i$ and $j$, you know whether soldier $j$ is right front of soldier $i$. Determine whether at least one configuration satisfies the given information. If one exists, compute the minimum number of soldiers in the first row (the row in front of every other row).

The first line contains one integer $N$, the number of soldiers. The second line contains $N$ integers $h_1, h_2, \ldots, h_N$, where $h_i$ is the height of soldier $i$. Each of the following $N$ lines contains $N$ characters. The $j$-th character of the $i$-th of these lines is '1' if soldier $j$ is right front of soldier $i$, and '0' otherwise.

Print one number, the minimum possible number of soldiers in the first row. If no configuration satisfies the given information, print $-1$.

• $2 \le N \le 10^3$
• $1 \le h_i \le 10^9$
• All $h_i$ are distinct.
• $s_{ij}$ is '0' or '1'.
• $s_{ii}$ is '0' for all $i$ in $1, 2, \ldots, N$.