背景

魔术师艾文准备开启他的全国巡演。他有两套完全不同的魔术节目——「幻影之夜」和「星辰奇缘」。艾文计划在若干座城市演出，每座城市恰好演出其中一场。由于相邻城市之间观众流动频繁，为了避免同一批观众短期内看到重复节目、影响票房，任何两座有直接公路相连的城市都不能安排同一套节目。

现在，艾文拿到了各城市的人口数据与城市间的公路连接图。他希望尽可能让观看「幻影之夜」的总人数与观看「星辰奇缘」的总人数接近，从而在两套节目之间保持宣传热度平衡。你的任务是帮他计算出这两个总人数之差的最小可能值。

题目描述

给定 $n$ 座城市，编号为 $0$ 到 $n-1$。第 $i$ 座城市的人口为 $p_i$。

城市之间的公路连接情况由一个 $n\times n$ 的矩阵 $roads$ 描述：$roads[i][j]=1$ 表示城市 $i$ 与城市 $j$ 之间有一条公路，$roads[i][j]=0$ 表示没有。该矩阵满足：

• 对角线元素为 $0$（城市不与自身相连）；
• 矩阵对称（公路是双向的）；
• 数据保证存在一种方案，使得任意相邻城市安排不同节目。

你需要为每座城市选择一场节目（标记为 $1$ 或 $2$），使得任意相邻城市标记不同，并且

$$\left|\sum_{\text{标记为 }1} p_i \;-\; \sum_{\text{标记为 }2} p_i\right|$$

最小。输出这个最小值。

输入格式

第一行一个整数 $n$，表示城市数量。

接下来 $n$ 行，每行一个长度为 $n$ 的字符串，仅由 0 和 1 组成，表示公路连接矩阵。

最后一行 $n$ 个整数 $p_0, p_1, \dots, p_{n-1}$，表示每座城市的人口。

输出格式

输出一个整数，表示观看两场节目的总人数之差的最小可能值。

样例

样例 1

2
01
10
15 20

5

样例 2

4
0100
1000
0001
0010
2 4 2 4

0

样例 3

3
000
000
000
6 7 15

2

数据范围

• $1 \le n \le 50$；
• $0 \le p_i \le 20$；
• $roads$ 中只包含 0 和 1；
• $roads[i][i]=0$，且 $roads[i][j]=roads[j][i]$；
• 保证存在满足条件的节目安排方案。