题目描述

题意翻译

现在有$n$人，每人都拥有1个冰箱。现提供$m$条铁链，每条铁链可以连接两个冰箱，且只有这两个冰箱的主人可以解锁这条铁链。

只有冰箱上所有铁链都被解锁后，才能打开这个冰箱，如果一个冰箱被铁链加固后只有它的主人可以独自打开它，那么我们称这个冰箱是“私有的”。

另外，如果只有2个冰箱，那么无论有多少条铁链，两个冰箱都不是“私有的”，因为这两个人都可以独自打开对方的冰箱。

在图例中有4个冰箱和5条铁链，所有冰箱都是“私有的”。1号冰箱的主人可以解锁连接1-2和连接1-4的铁链，1号冰箱只能被它的主人独自打开，或者被2号和4号同时打开。

每个冰箱都有一个重量，记为$a_1,a_2,a_3,\ldots,a_n$。如果要给u号和v号冰箱用铁链加固，需要花费$a_u+a_v$元。两个冰箱之间可以有多条铁链加固。

请求出，在将$m$条铁链全部被使用后，所有冰箱是否可能均为“私有的”，如果可能，那么求出最小花费是多少。

输入格式

每个测试点包含多组测试数据

第一行输入数据组数$T$($1 \le T \le 10$)，接下来输入$T$组数据，每组数据格式如下：

第一行包含两个正整数$n,m$($2 \le n \le 1000,1 \le m \le n$)，分别代表人数和铁链数量。

第二行包含$n$个整数$a_1,a_2,a_3,\ldots,a_n$($0 \le a_i \le 1000$)，代表每个冰箱的重量。

输出格式

对于每组测试数据：

• 如果不能使每个冰箱都是“私有的”，输出-1。

• 否则，输出一个整数$c$，代表最小花费。接下来每行，对于第$i$行，输出第$i$条铁链连接的两个冰箱。两个冰箱之间可以有任意多的铁链相连。

如果答案不唯一，输出任意一组。

样例

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

8
1 2
4 3
3 2
4 1
-1
12
3 2
1 2
3 1