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
mod=10**9+7
import sys 
# sys.setrecursionlimit(10**6) 
from sys import stdin, stdout
import bisect            #c++ upperbound
import math
import heapq
def modinv(n,p):
    return pow(n,p-2,p)
def cin():
    return map(int,sin().split())
def ain():                           #takes array as input
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
"""*******************************************************"""
 
def main():
    t=inin()
    for _ in range(t):
        n,p=cin()
        a=ain()
        if(p<n or n==2):
            print(-1)
            continue
        else:
            b=[]
            for i in range(n):
                b.append((a[i],i))
            b.sort()
            jj=b[0][0]
            j=b[0][1]
            kk=b[1][0]
            k=b[1][1]
            x=sum(a)*2
            y=jj+kk
            y=y*(p-n)
            print(x+y)
            for i in range(n-1):
                print(i+1,i+2)
            print(n,1)
            for i in range(p-n):
                print(j+1,k+1)
######## Python 2 and 3 footer by Pajenegod and c1729
 
# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.
 
# So on cf, use PyPy2 for best string performance.
 
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
 
import os, sys
from io import IOBase, BytesIO
 
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'
 
# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A
 
if __name__== "__main__":
  main()