题目描述

新一届高中生物学竞赛就要开始了，你所在的高中学校决定举办一场选拔性校赛，为了营造最好的比赛氛围，决定委托 bwgg 用经费请一些大学生宣传比赛（毕竟大学生最物美价廉）。

现在一共有 $n$ 名大学生，他们按 $1,2,3,...,n$ 编号，其中 $1$ 号是 bwgg 。

俗话说："我朋友的朋友也是我的朋友"。 bwgg 决定先向他的朋友宣传比赛，再让他们向他们的朋友宣传比赛...以此类推。

每个大学生都有一个期望值(包括 bwgg 自己)，如果 bwgg 给他不少于期望值的经费，那么他就会向他的所有朋友宣传比赛， bwgg 想向所有大学生宣传比赛，请帮 bwgg 计算需要的最少经费是多少？

输入格式

本题有 $\textbf{多组数据}$ ，第一行需要先读入一个 $T$ $(1 \leq T \leq 100)$ 表示测试数据组数。

对于每一组数据：

第一行两个整数 $n \enspace m$ $(2 \leq n \leq 20,0 \leq m \leq 100)$ ，表示大学生数与朋友关系数。

第二行 $n$ 个整数 $v_i$ $(0\leq v_{i}\leq 10^6)$ ，表示每个大学生的期望值。

接下来 $m$ 行，每行两个整数 $a_i \enspace b_i$ $(1 \leq a_i,b_i \leq n,a_i \neq b_i)$ 表示 $a_i$ 号大学生与 $b_i$ 号大学生是朋友。

输出格式

如果 bwgg 无法让所有大学生知道比赛，输出 $-1$ ；否则输出需要的最少经费。

样例

2
4 5
1 2 3 4
1 2
1 3
2 3
2 4
3 4
5 4
2 2 2 2 2
1 2
1 3
2 3
4 5

3
-1

样例解释

对于样例第 $1$ 组， bwgg 向 $2$ 号和 $3$ 号宣传比赛（需要 $1$ 经费）。请 $2$ 号向 $4$ 号宣传比赛（需要 $2$ 经费），共需要 $3$ 经费。

对于样例第 $2$ 组，无论如何都宣传不到学生 $4$ 和 $5$ 。