众所周知，Naomi 不擅长数学，但她每天都在练习数学题。以下是她遇到的一个问题。

Naomi 有一个包含 $n$ 个节点（编号从 $1$ 到 $n$）和 $m$ 条边的无向连通图。每条边的长度均为 $1$。图中的每个节点都有一个特殊值，第 $i$ 个节点的值记为 $A[i]$。她定义 $dist[i]$ 为第 $i$ 个节点与第 $1$ 个节点之间的最短路径长度，特别地，$dist[1]=0$。

然后，她定义该图的代价为 $\sum_{i=1}^{n}(A[i]-dist[i])^2$。

Naomi 想要通过在图中插入一些新边（新边的长度也应为 $1$）来最小化图的代价。她可以选择不插入任何边，也可以插入任意数量的新边。

你能帮帮她吗？

输入格式

输入包含不超过 $10$ 组测试数据。

对于每组测试数据，第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 40, 0 \le m \le 1600$)。

接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n$)，表示第 $x$ 个节点和第 $y$ 个节点之间有一条边。

测试数据的最后一行包含 $n$ 个整数，描述数组 $A$，其中每个元素满足 $0 \le A[i] \le 1000$。

输出格式

对于每组测试数据，输出一行，表示该图的最小代价。

样例

样例输入 1

4 3
1 2
2 3
3 4
0 3 3 3

样例输出 1

5