题目描述

$n$ 个点的无向联通图。在上面添加若干条边后，设 $f_i=(dis_i-a_i)^2$，$dis_i$ 为 $1$ 到 $i$ 的最短距离，最小化 $\sum f_i$。

保证这个图是随机生成的。

输入格式

第一行一个正整数 $n$。$(1\le n\le 500)$

接下来一个矩阵，每个字符都是 Y 或 N，为这个图的邻接矩阵。保证 Y 字符数小于等于 $10^4$。

接下来一行 $n$ 个正整数，第 $i$ 个为 $a_i$。保证 $a_1=0,a_i\le n$。

输出格式

一行一个数表示答案。

样例

样例输入 1

5
NNYYN
NNYNN
YYNNY
YNNNN
NNYNN
0 2 1 3 2

样例输出 1

4

样例输入 2

30
NYYNNYNYNNNNNNNNNNNNNYNYYYNNNN
YNYNNNYNYNNNYNNNYNNNNNYNNYNYNN
YYNYYNNNYNYYNNNNNNNNNNYNNNNNNN
NNYNNNNNYNNNNYYNNYNYNYNNNNNYNN
NNYNNNYYNNNYNNNNNNNYNNNNNNNYNN
YNNNNNNYYNNNNNYNNNNNNNNNNNYNNN
NYNNYNNNNYNNNNYNNNNNNNNNNNNYYN
YNNNYYNNNNYYNNNYYNYNYNNYNNNNYN
NYYYNYNNNNYNNYNYNYNNNNYNYNNNNN
NNNNNNYNNNNNNNYNNNYNYYNNNNNNNN
NNYNNNNYYNNNNNNNNNNNNNNYNYNNNN
NNYNYNNYNNNNYYNNNYYYYNYNNNNNNN
NYNNNNNNNNNYNNNNNNYNNNYNYNNNNN
NNNYNNNNYNNYNNNYNNNNNNNNNNNNNN
NNNYNYYNNYNNNNNNNNNNNYNYNYNYNN
NNNNNNNYYNNNNYNNNYNNNNNNNNNNNN
NYNNNNNYNNNNNNNNNNNYNNYYNYNNNY
NNNYNNNNYNNYNNNYNNNNNYYNNNNNNN
NNNNNNNYNYNYYNNNNNNNNNNNNNNNNN
NNNYYNNNNNNYNNNNYNNNNNNNYNNNNN
NNNNNNNYNYNYNNNNNNNNNNNNNNYNYN
YNNYNNNNNYNNNNYNNYNNNNNNNNNNNN
NYYNNNNNYNNYYNNNYYNNNNNNNNNNNN
YNNNNNNYNNYNNNYNYNNNNNNNNYNNNN
YNNNNNNNYNNNYNNNNNNYNNNNNNNNYN
YYNNNNNNNNYNNNYNYNNNNNNYNNNNNN
NNNNNYNNNNNNNNNNNNNNYNNNNNNNNN
NYNYYNYNNNNNNNYNNNNNNNNNNNNNNN
NNNNNNYYNNNNNNNNNNNNYNNNYNNNNN
NNNNNNNNNNNNNNNNYNNNNNNNNNNNNN
0 0 0 2 2 3 2 7 0 1 6 7 11 12 10 7 10 10 14 18 16 15 13 9 7 15 23 26 5 23

样例输出 2

3101