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.io.*;
import java.io.FileWriter; 

// Solution

public class Main 
{    
  public static void main (String[] argv) 
  {
	  new Main();
  } 
     
  
  boolean test = false;  
  
  final int MOD = 998244353;  //1000000007;  
  
  
  final int S = 100000;
  final int N = 200001;
  
  //final int S = 0;
  //final int N = 32;
  int[] tree = new int[4*N];
  int[] lazy = new int[4*N];
  final int INF = Integer.MAX_VALUE;
  
  public Main()   {
	FastReader in = new FastReader(new BufferedReader(new InputStreamReader(System.in)));
	
     
    //FastReader in = new FastReader(new BufferedReader(new FileReader("Main.in")));   
    
    int nt = in.nextInt();    
    //int nt = 1;
    StringBuilder sb = new StringBuilder();
    
    
    for (int it = 0; it < nt; it++) 
    {
       int n = in.nextInt();
       int m = in.nextInt();
       int[] a = new int[n];
       for (int i = 0; i < n; i++) a[i] = in.nextInt();
       int m1 = 0, m2 = 1, sum = a[0] + a[1];
       if (a[0] > a[1]){
           m1 = 1;
           m2 = 0;
       }
       for (int i = 2; i < n; i++) {
           if (a[i] <= a[m1]) {
               m2 = m1;
               m1 = i;
           }else if (a[i] <a[m2]) m2 = i;
           sum += a[i];
       }
       int ans = 0;
       if (m < n || n <= 2) sb.append("-1\n");
       else {
           ans = sum * 2 + (m-n) * (a[m1] + a[m2]);
           sb.append(ans + "\n");
           for (int i = 1; i <= n-1; i++)
           {
               sb.append(i + " " + (i+1) + "\n");
               
           }
           sb.append(1 + " " + (n) + "\n");
           for (int i = 0; i < m - n; i++)
               sb.append((1+m1) + " " + (1+m2) + "\n");
       }
       
       
    }
    System.out.print(sb);
  }
  
  private int f(int fr, int to)
  {
      if (fr == to) return 0;
      
      if (fr > to) return f(to, fr);
      
      int d = to - fr;
      int c = d / 5;
      d = d % 5;
      if (d == 1 || d == 2) return c + 1;
      if (d == 4 || d == 3) return c + 2;
      return c;      
  }
  
  private void rangeUpdate(int node, int lo, int hi, int fr, int to, int val)
  {
      pushDown(node, lo, hi);
      
      if (lo == fr && hi == to)
      {
          lazy[node] = val;
          tree[node] = val;
          return;
      }
      
      int mid = (lo + hi) / 2;
      
      if (to <= mid) {
          rangeUpdate(node * 2, lo, mid, fr, to, val);
      }else if (fr > mid) {
          rangeUpdate(node * 2 + 1, mid + 1, hi, fr, to, val);
      }else {
          rangeUpdate(node * 2, lo, mid, fr, mid, val);
          rangeUpdate(node * 2 + 1, mid + 1, hi, mid + 1, to, val);
      }
      
      //combine
      combine(node, lo, hi);
  }
  
  private int query(int node, int lo, int hi, int fr, int to)
  {   
     if (lazy[node] != -1)
          return tree[node];
      
     if (lo == fr && hi == to) {
          //System.out.println("found " + tree[node]);
          return tree[node];
      }
      
      int mid = (lo + hi) / 2;
      
      if (to <= mid) return query(node * 2, lo, mid, fr, to);
      if (mid < fr) return query(node * 2 + 1, mid + 1, hi, fr, to);
      
      return Math.min(query(node * 2, lo, mid, fr, mid),
                      query(node * 2 + 1, mid + 1, hi, mid + 1, to)); 
      
  }
  
  private void pushDown(int node, int lo, int hi)
  {
      if (lo >= hi || lazy[node] == -1) return;
      
      lazy[node * 2] = lazy[node];
      lazy[node * 2 + 1] = lazy[node];
      tree[node * 2] = lazy[node];
      tree[node * 2 + 1] = lazy[node];
      
      /* clear lazy of node */
      lazy[node] = -1;
  }
  
  private void combine(int node, int lo, int hi)
  {
      if (lo >= hi) return;
      
      tree[node] = Math.min(tree[node * 2], tree[node * 2 + 1]);
  }
  
  
  private int inv(int v)
  {
      return pow(v, MOD-2);
  }
  
  private int pow(long v, int p)
  {
      long ans = 1;
      while (p > 0)
      {
          if (p % 2 == 1)
              ans = ans * v % MOD;
          v = v * v % MOD;
          p = p / 2;
      }
      return (int)ans;
  }
  
  private double dist(double x, double y, double xx, double yy)
  {
      return Math.sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));
  }
  

  
 
  private int mod_add(int a, int b) {
      int v = a + b;
      if (v >= MOD) v -= MOD;
      return v;
  }
  
  
  private long overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
      if (x1 > x3) return overlap(x3, y3, x4, y4, x1, y1, x2, y2);
      
      if (x3 > x2 || y4 < y1 || y3 > y2) return 0L;
      
      //(x3, ?, x2, ?)
      int yL = Math.max(y1, y3);
      int yH = Math.min(y2, y4); 
      int xH = Math.min(x2, x4);
      
      return f(x3, yL, xH, yH);
  }
  //return #black cells in rectangle
  private long f(int x1, int y1, int x2, int y2) {
      long dx = 1L + x2 - x1;
      long dy = 1L + y2 - y1;
      if (dx % 2 == 0 || dy % 2 == 0 || (x1 + y1) % 2 == 0) 
          return 1L * dx * dy / 2;
      return 1L * dx * dy / 2 + 1;
  }
  
  private int distM(int x, int y, int xx, int yy) {
      return abs(x - xx) + abs(y - yy);
  }
  
  private boolean less(int x, int y, int xx, int yy) {
      return x < xx || y > yy;
  }
  
  private int mul(int x, int y) {
      return (int)(1L * x * y % MOD);
  }
  
  
 
  
  private int nBit1(int v) {
      int v0 = v;
      int c = 0;
      while (v != 0) {
          ++c;
          v = v & (v - 1);
      }
      return c;
  }
  
  private long abs(long v) {
      return v > 0 ? v : -v;
  }
  
  private int abs(int v) {
      return v > 0 ? v : -v;
  }
  
  private int common(int v) {
      int c = 0;
      while (v != 1) {
          v = (v >>> 1);
          ++c;
      }
      
      return c;
  }
  
  private void reverse(char[] a, int i, int j) {
      while (i < j) {
          swap(a, i++, j--);
      }
  }
  
  private void swap(char[] a, int i, int j) {
      char t = a[i];
      a[i] = a[j];
      a[j] = t;
  }
  
  private int gcd(int x, int y) {
      if (y == 0) return x;
      return gcd(y, x % y);
  }
  private long gcd(long x, long y) {
      if (y == 0) return x;
      return gcd(y, x % y);
  }
  private int max(int a, int b) {
      return a >  b ? a : b;
  }
  
  private long max(long a, long b) {
      return a >  b ? a : b;
  }
  
  private int min(int a, int b) {
      return a >  b ? b : a;
  }
  
  private long min(long a, long b) {
      return a >  b ? b : a;
  }
  
  static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader(BufferedReader in)
        {            
            br = in;
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    String line = br.readLine();
                    if (line == null || line.length() == 0) return "";
                    st = new StringTokenizer(line);
                }
                catch (IOException  e)
                {
                    return "";
                    //e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                return null;
                //e.printStackTrace();
            }
            return str;
        }
    }
}