Hanh lives in a shared apartment. There are n people (including Hanh) living there, each has a private fridge. 

n fridges are secured by several steel chains. Each steel chain connects two different fridges and is protected by a digital lock. The owner of a fridge knows passcodes of all chains connected to it. A fridge can be open only if all chains connected to it are unlocked. For example, if a fridge has no chains connected to it at all, then any of n people can open it.

<image> For exampe, in the picture there are n=4 people and 5 chains. The first person knows passcodes of two chains: 1-4 and 1-2. The fridge 1 can be open by its owner (the person 1), also two people 2 and 4 (acting together) can open it.

The weights of these fridges are a_1, a_2, …, a_n. To make a steel chain connecting fridges u and v, you have to pay a_u + a_v dollars. Note that the landlord allows you to create multiple chains connecting the same pair of fridges. 

Hanh's apartment landlord asks you to create exactly m steel chains so that all fridges are private. A fridge is private if and only if, among n people living in the apartment, only the owner can open it (i.e. no other person acting alone can do it). In other words, the fridge i is not private if there exists the person j (i ≠ j) that the person j can open the fridge i.

For example, in the picture all the fridges are private. On the other hand, if there are n=2 fridges and only one chain (which connects them) then both fridges are not private (both fridges can be open not only by its owner but also by another person).

Of course, the landlord wants to minimize the total cost of all steel chains to fulfill his request. Determine whether there exists any way to make exactly m chains, and if yes, output any solution that minimizes the total cost. 

Input

Each test contains multiple test cases. The first line contains the number of test cases T (1 ≤ T ≤ 10). Then the descriptions of the test cases follow.

The first line of each test case contains two integers n, m (2 ≤ n ≤ 1000, 1 ≤ m ≤ n) — the number of people living in Hanh's apartment and the number of steel chains that the landlord requires, respectively.

The second line of each test case contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 10^4) — weights of all fridges.

Output

For each test case:

  * If there is no solution, print a single integer -1. 
  * Otherwise, print a single integer c — the minimum total cost. The i-th of the next m lines contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i), meaning that the i-th steel chain connects fridges u_i and v_i. An arbitrary number of chains can be between a pair of fridges. 



If there are multiple answers, print any.

Example

Input


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


Output


8
1 2
4 3
3 2
4 1
-1
12
3 2
1 2
3 1
import java.util.*; 
import java.lang.*; 
import java.io.*; 
  
public class Graph 
{ 
    // A class to represent a graph edge 
    class Edge implements Comparable<Edge> 
    { 
        int src, dest, weight; 
  
        // Comparator function used for sorting edges  
        // based on their weight 
        public int compareTo(Edge compareEdge) 
        { 
            return this.weight-compareEdge.weight; 
        } 
    }; 
  
    // A class to represent a subset for union-find 
    class subset 
    { 
        int parent, rank; 
    }; 
  
    int V, E;    // V-> no. of vertices & E->no.of edges 
    Edge edge[]; // collection of all edges 
  
    // Creates a graph with V vertices and E edges 
    Graph(int v, int e) 
    { 
        V = v; 
        E = e; 
        edge = new Edge[E]; 
        for (int i=0; i<e; ++i) 
            edge[i] = new Edge(); 
    } 
  
    // A utility function to find set of an element i 
    // (uses path compression technique) 
    int find(subset subsets[], int i) 
    { 
        // find root and make root as parent of i (path compression) 
        if (subsets[i].parent != i) 
            subsets[i].parent = find(subsets, subsets[i].parent); 
  
        return subsets[i].parent; 
    } 
  
    // A function that does union of two sets of x and y 
    // (uses union by rank) 
    void Union(subset subsets[], int x, int y) 
    { 
        int xroot = find(subsets, x); 
        int yroot = find(subsets, y); 
  
        // Attach smaller rank tree under root of high rank tree 
        // (Union by Rank) 
        if (subsets[xroot].rank < subsets[yroot].rank) 
            subsets[xroot].parent = yroot; 
        else if (subsets[xroot].rank > subsets[yroot].rank) 
            subsets[yroot].parent = xroot; 
  
        // If ranks are same, then make one as root and increment 
        // its rank by one 
        else
        { 
            subsets[yroot].parent = xroot; 
            subsets[xroot].rank++; 
        } 
    } 
  
    // The main function to construct MST using Kruskal's algorithm 
    void KruskalMST(int K,int[]nodes) 
    { 
        Edge result[] = new Edge[V];  // Tnis will store the resultant MST 
        int e = 0;  // An index variable, used for result[] 
        int i = 0;  // An index variable, used for sorted edges 
        for (i=0; i<V; ++i) 
            result[i] = new Edge(); 
  
        // Step 1:  Sort all the edges in non-decreasing order of their 
        // weight.  If we are not allowed to change the given graph, we 
        // can create a copy of array of edges 
        Arrays.sort(edge); 
        
        Integer start=0;
        Integer end=0;
        
        int counter=0;
        long cost=0;
        
        ArrayList<Edge>rem=new ArrayList<>();
        
        // for(int p=0;i<edge.length;i++)
        // {
        //     rem.add(edge[i]);
        // }
  
        int[]indegree=new int[V];
        // Allocate memory for creating V ssubsets 
        subset subsets[] = new subset[V]; 
        for(i=0; i<V; ++i) 
            subsets[i]=new subset(); 
  
        // Create V subsets with single elements 
        for (int v = 0; v < V; ++v) 
        { 
            subsets[v].parent = v; 
            subsets[v].rank = 0; 
        } 
  
        i = 0;  // Index used to pick next edge 
  
        // Number of edges to be taken is equal to V-1 
        while (e < V - 1) 
        { 
            // Step 2: Pick the smallest edge. And increment  
            // the index for next iteration 
            Edge next_edge = new Edge(); 
            if(i<edge.length)
            next_edge = edge[i++]; 
            else
            next_edge=rem.remove(0);
  
            int x = find(subsets, next_edge.src); 
            int y = find(subsets, next_edge.dest); 
  
            // If including this edge does't cause cycle, 
            // include it in result and increment the index  
            // of result for next edge 
            if (x != y && indegree[next_edge.src]<2 && indegree[next_edge.dest]<2) 
            { 
                
                result[e++] = next_edge; 
                Union(subsets, x, y); 
                
                cost=cost+next_edge.weight;
                
                indegree[next_edge.src]++;
                indegree[next_edge.dest]++;
                //System.out.println(next_edge.src+" "+next_edge.dest);
                K--;
            } 
            else
            {
                rem.add(next_edge);
            }
            // Else discard the next_edge 
        } 
        
        if(K<=0)
        {
            System.out.println("-1");
            
        }
        
            else if(K==1)
            {
                for(int z=0;z<indegree.length;z++)
                {
                    if(indegree[z]==1 && start==null)
                    {
                        start=z;
                    }
                    else if(indegree[z]==1)
                    {
                        end=z;
                        break;
                    }
                }
                cost=cost+nodes[start]+nodes[end];
                K--;
                System.out.println(cost);
                System.out.println((start+1)+" "+(end+1));
                for (i = 0; i < e; ++i) 
                System.out.println((result[i].src+1)+" "+(result[i].dest+1)); 
            }
       
        }
  
    // Driver Program 
    public static void main (String[] args) 
    { 
  
       Scanner sc=new Scanner(System.in);
       int tc=sc.nextInt();
       
       for(int t=0;t<tc;t++)
       {
          
        int V = sc.nextInt();  // Number of vertices in graph 
        int E = sc.nextInt();  // Number of edges in graph 
        Graph graph = new Graph(V, E); 
  
        int[]nodes=new int[V];
        long cost=0;
        for(int i=0;i<V;i++)
        {
            nodes[i]=sc.nextInt();
            cost=cost+2*nodes[i];
        }
        
        
         if(V==2 || E<V)
           {
               System.out.println("-1");
               continue;
           }
        
        for(int i=0;i<V;i++)
        {
            for(int j=0;j<V;j++)
            {
                if(i!=j)
                {
                    graph.edge[i].src=i;
                    graph.edge[i].dest=j;
                    graph.edge[i].weight=nodes[i]+nodes[j];
                }
            }
        }
        
        System.out.println(cost);
        for(int i=0;i<V-1;i++)
        {
            System.out.println((i+1)+" "+(i+2));
        }
        
        System.out.println(V+" "+"1");
 
    
        //graph.KruskalMST(E,nodes); 
       }
    } 
} 
