지루한 Dreamoon

Dreamoon은 올해 군 복무 중이다. 군대의 모든 것은 지루하다. 군 생활을 더 재미있게 만들려고 Dreamoon은 군에서 겪은 일 일부를 프로그래밍 대회 문제로 바꾸기로 했다.

지휘관은 보통 병사들을 키 순서대로 여러 줄에 세운다. 병사 배치 규칙은 다음과 같다.

• 병사 $A$와 $B$가 서로 다른 줄에 서 있고 $A$의 줄이 $B$의 줄보다 앞에 있으면, $A$는 $B$보다 키가 작다.
• 병사 $A$와 $B$가 같은 줄에 서 있고 $A$가 $B$보다 오른쪽에 있으면, $A$는 $B$보다 키가 작다.
• 어떤 두 줄을 고르더라도 두 줄의 병사 수 차이는 최대 $1$이다.
• 어떤 두 줄을 고르더라도 앞줄의 병사 수는 뒷줄의 병사 수와 같거나 많다.

Dreamoon은 이 성질들을 알아챈 뒤 다음 문제를 떠올렸다.

서로 다른 두 병사 $A$와 $B$에 대해, $A$의 줄이 $B$의 줄보다 앞에 있지 않고, $B$의 줄에서 $B$보다 오른쪽에 있는 병사 수가 $A$의 줄에서 $A$보다 오른쪽에 있는 병사 수보다 많지 않으면, $B$를 $A$의 right front라고 한다.

전체 병사 수도, 줄이 몇 개인지도 모른다. 번호가 $1$부터 $N$까지인 $N$명 병사의 키는 알고 있다. 서로 다른 두 번호 $i$와 $j$에 대해, 병사 $j$가 병사 $i$의 right front인지도 알고 있다. 주어진 정보를 모두 만족하는 배치가 하나라도 있는지 확인하라. 있다면 가장 앞줄(다른 모든 줄보다 앞에 있는 줄)에 서는 병사 수의 최솟값을 구하라.

첫 줄에 병사의 수 $N$이 주어진다. 둘째 줄에는 $N$개의 정수 $h_1, h_2, \ldots, h_N$이 주어지며, $h_i$는 $i$번 병사의 키다. 이어지는 $N$개 줄에는 각각 $N$개의 문자가 주어진다. $i$번째 줄의 $j$번째 문자는 병사 $j$가 병사 $i$의 right front이면 '1', 아니면 '0'이다.

가능한 배치 중 첫 줄에 서는 병사 수의 최솟값을 한 개의 수로 출력한다. 주어진 정보를 만족하는 배치가 없으면 $-1$을 출력한다.

• $2 \le N \le 10^3$
• $1 \le h_i \le 10^9$
• 모든 $h_i$는 서로 다르다.
• $s_{ij}$는 '0' 또는 '1'이다.
• 모든 $i$($1, 2, \ldots, N$)에 대해 $s_{ii}$는 '0'이다.