Byteasar 国王认为，Byteotia 这片拥有美丽景色的土地应该吸引大量游客，游客们应该花费大量的金钱，而这些钱最终应该流入皇家国库。但现实却不尽如人意。于是，国王指示他的顾问调查这个问题。顾问发现，外国人因为 Byteotia 稀疏的道路网络而对这里敬而远之。

Byteotia 有 $n$ 个城镇，由 $m$ 条双向道路连接，每条道路连接两个不同的城镇。道路可能穿过风景如画的立交桥，也可能穿过不那么美观的隧道。不保证每个城镇都能从其他任何城镇到达。

顾问观察到，目前的道路网络不允许进行长途旅行。具体来说，无论从哪里开始旅程，如果不经过某个城镇两次，就不可能访问超过 $10$ 个城镇。

由于国库资金有限，目前不会修建新的道路。相反，Byteasar 决定建立一个旅游信息点（TIP）网络，由工作人员负责宣传现有的短途旅行。对于每个城镇，要么在该城镇，要么在与该城镇直接相连的城镇之一中，必须设有一个 TIP。此外，每个城镇建立 TIP 的成本是已知的。请帮助国王找到满足上述条件且成本最低的 TIP 建设方案。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 20\,000$, $0 \le m \le 25\,000$)，由一个空格分隔，分别表示 Byteotia 的城镇数量和道路数量。城镇编号从 $1$ 到 $n$。输入的第二行包含 $n$ 个整数 $c_{1}, c_{2}, \dots, c_{n}$ ($0 \le c_{i} \le 10\,000$)，由空格分隔；数字 $c_{i}$ 表示在第 $i$ 号城镇建立 TIP 的成本。

接下来是 Byteotia 道路网络的描述。接下来的 $m$ 行中，第 $i$ 行包含两个整数 $a_{i}, b_{i}$ ($1 \le a_{i} < b_{i} \le n$)，由一个空格分隔，表示第 $a_{i}$ 号城镇和第 $b_{i}$ 号城镇之间有一条道路。任意两个城镇之间最多只有一条（直接）道路。

在总分占比 $20\%$ 的测试中，满足 $n \le 20$。

输出格式

你的程序应向标准输出打印一个整数：建立所有 TIP 的总成本。

样例

输入 1

6 6
3 8 5 6 2 2
1 2
2 3
1 3
3 4
4 5
4 6

输出 1

7

说明

为了达到最小成本，应在第 1、5 和 6 号城镇建立 TIP（成本为 $3+2+2=7$）。