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$ 的“右前方”。

你不知道总共有多少名士兵，也不知道这些士兵被排成了多少排。但你掌握了 $N$ 名士兵的信息，编号从 $1$ 到 $N$。已知这些士兵的身高。对于任意两个不同的编号 $i$ 和 $j$，你知道士兵 $j$ 是否在士兵 $i$ 的“右前方”。请检查是否存在至少一种满足给定信息的排列方案。如果存在，请计算第一排（在所有其他排前面的那一排）中最少可能有多少名士兵。

输入格式

第一行包含一个整数 $N$，表示你有 $N$ 名士兵的信息。 第二行包含 $N$ 个整数 $h_1, h_2, \dots, h_N$。其中 $h_i$ 表示第 $i$ 名士兵的身高。 接下来的 $N$ 行，每行包含 $N$ 个字符。第 $i$ 行的第 $j$ 个字符如果为 ‘1’，则表示士兵 $j$ 在士兵 $i$ 的“右前方”；否则为 ‘0’。

• $2 \le N \le 10^3$
• $1 \le h_i \le 10^9$
• 所有 $h_i$ 互不相同
• $s_{ij} = \text{‘0’ 或 ‘1’}$
• $s_{ii} = \text{‘0’}$，对于所有 $i \in \{1, 2, \dots, N\}$

输出格式

输出一个数字，表示第一排（在所有其他排前面的那一排）中最少可能有多少名士兵。如果不存在满足给定信息的排列方案，则输出 $-1$。

样例

样例输入 1

3
1 2 3
000
000
000

样例输出 1

3

样例输入 2

3
1 2 3
000
100
110

样例输出 2

1