Dreamoon serves in the military this year. Everything in the military is boring. In order to make military life more interesting, Dreamoon decided to transform some of his military experiences into programming competition problems.
The leaders usually order soldiers to stand in several rows ordered by their heights. The rules of arrangement of soldiers are as follows:
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 the 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 don't know how many soldiers there are in total, and you don't know how many rows these soldiers are arranged into. But you have some information about certain N soldiers, numbered from 1 through N. You are given the heights of these soldiers. And for any two distinct numbers i and j, you know whether soldier j is right front of i. Please inspect whether there exists at least one possible configuration satisfying the given information. If possible, you should calculate the minimum number of soldiers in the first row (the row in front of every other row).
The first line of input contains one integer N indicating that you have information of N soldiers. The second line of input consists of N integers h1, h2, ..., hN. Here, hi indicates the height of i-th soldier. Note that the unknown heights of the soldiers are allowed to be non-integers.
Each of the following N lines contains N characters. The j-th character in the i-th of these lines is '_1_' if soldier j is right front of soldier i; otherwise, it is '_0_'.
Output one number indicating the minimum possible number of soldiers in the first row (the row in front of every other row). If there is no possible configuration satisfying the given information, output - 1 instead.
## Input
The first line of input contains one integer N indicating that you have information of N soldiers. The second line of input consists of N integers h1, h2, ..., hN. Here, hi indicates the height of i-th soldier. Note that the unknown heights of the soldiers are allowed to be non-integers.Each of the following N lines contains N characters. The j-th character in the i-th of these lines is '_1_' if soldier j is right front of soldier i; otherwise, it is '_0_'. 2 ≤ N ≤ 103 1 ≤ hi ≤ 109 all hi are distinct for all i in 1, 2, ..., N
## Output
Output one number indicating the minimum possible number of soldiers in the first row (the row in front of every other row). If there is no possible configuration satisfying the given information, output - 1 instead.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of known soldiers.
Let $ h = (h_1, h_2, \dots, h_N) \in \mathbb{R}^N $ be the vector of their heights.
Let $ R \in \{0,1\}^{N \times N} $ be the adjacency matrix where $ R[i][j] = 1 $ iff soldier $ j $ is *right front* of soldier $ i $.
**Constraints**
1. For all $ i, j \in \{1, \dots, N\} $, if $ R[i][j] = 1 $, then:
- $ h_j \leq h_i $ (soldier $ j $ is not taller than soldier $ i $),
- The row of $ j $ is not in front of the row of $ i $,
- The number of soldiers to the right of $ j $ in its row $ \leq $ the number of soldiers to the right of $ i $ in its row.
2. The arrangement of all soldiers (known and unknown) must satisfy:
- Soldiers are arranged in rows ordered by increasing row index (row 1 is frontmost),
- Within each row, soldiers are ordered left to right by increasing index (arbitrary assignment),
- Heights are non-decreasing from front to back rows and non-decreasing left to right within a row.
3. The *right front* relation must be consistent with the global row and position assignment.
**Objective**
Determine the minimum possible number of soldiers in row 1 (front row) over all valid configurations satisfying the above constraints. If no such configuration exists, output $ -1 $.