题目描述

一座小岛上有 $n$ 座城市，编号为 $1\sim n$，部分城市之间有双向道路。最初所有城市都彼此独立。

后来城市 $s$ 和城市 $t$ 分别建立了两个国家。记第一个国家当前拥有的城市集合为 $A$，第二个国家拥有的城市集合为 $B$，其他城市仍为独立城市。

对于城市集合 $X$，定义 $neigh(X)$ 为所有与 $X$ 中至少一座城市有道路相连、但不属于 $X$ 的城市集合。记城市 $i$ 的人口为 $popul(i)$，集合 $X$ 的总人口为 $popul(X)=\sum_{i\in X}popul(i)$。

若 $C$ 是一组当前独立城市，则第一个国家可以一次征服整个 $C$，当且仅当

$popul(A\cap neigh(C))>popul(C)+popul(B\cap neigh(C))$。

第二个国家可以一次征服整个 $C$，当且仅当

$popul(B\cap neigh(C))>popul(C)+popul(A\cap neigh(C))$。

每天早晨第一个国家行动，晚上第二个国家行动。若当前国家存在可征服的非空城市集合，它可以选择其中一种合法征服方案；若没有合法方案，则本次行动跳过。当双方都再也无法扩张时，过程结束。

第一个国家希望最终的 $popul(A)-popul(B)$ 尽可能大，第二个国家希望该值尽可能小。双方都采取最优策略。

求最终的 $popul(A)-popul(B)$。

输入格式

第一行三个整数 $n,s,t$，其中 $3\le n\le13$，$1\le s,t\le n$，且 $s\ne t$。

接下来 $n$ 行，每行 $n$ 个字符。第 $i$ 行第 $j$ 个字符为 1 表示城市 $i,j$ 间有双向道路，为 0 表示没有。

最后一行包含 $n$ 个整数 $popul(i)$，满足 $1\le popul(i)\le100000$。

输出格式

输出双方均采取最优策略时最终的 $popul(A)-popul(B)$。

样例

5 1 2
00111
00001
10010
10101
11010
12 100 5 5 7

-85