B. Замки для холодильников
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хань живет в общей квартире. Там живет $$$n$$$ человек (включая Ханя), у каждого из которых есть собственный холодильник.

$$$n$$$ холодильников защищены несколькими цепями. Каждая цепь соединяет два различных холодильника и защищена цифровым замком. Владелец холодильника знает коды доступа всех связанных с ним цепей. Холодильник может быть открыт только в том случае, если все цепи, подключенные к нему, разблокированы. Например, если холодильник вообще не имеет связанных с ним цепей, то его может открыть любой из $$$n$$$ человек.

Например, на рисунке есть $$$n=4$$$ людей и $$$5$$$ цепей. Первый человек знает пароль для двух цепей: $$$1-4$$$ и $$$1-2$$$. $$$1$$$-й холодильник может открыть его владелец ($$$1$$$-й человек), а также $$$2$$$-й и $$$4$$$-й (работая сообща) могут его открыть.

Цены этих холодильников равны $$$a_1, a_2, \ldots, a_n$$$. Чтобы сделать цепь, соединяющую холодильники $$$u$$$ и $$$v$$$, вы должны заплатить $$$a_u + a_v$$$ долларов. Обратите внимание, что владелец квартиры позволяет вам сделать несколько цепей, соединяющих одну и ту же пару холодильников.

Хозяин квартиры, в которой живет Хань, просит вас создать ровно $$$m$$$ цепей, чтобы все холодильники были защищены. Холодильник является защищенным тогда и только тогда, когда из $$$n$$$ людей, живущих в квартире, только владелец холодильника может открыть его (то есть больше никто, действуя самостоятельно, не сможет его открыть). Другими словами, $$$i$$$-й холодильник не защищен, если существует человек $$$j$$$ ($$$i \ne j$$$) такой, что $$$j$$$ в одиночку сможет открыть $$$i$$$-й холодильник.

Например, на рисунке все холодильники защищены. С другой стороны, если есть $$$n=2$$$ холодильника и только одна цепь (которая их соединяет), то оба холодильника не являются защищенными (оба холодильника могут быть открыты не только его владельцем, но и другим человеком).

Конечно, владелец хочет минимизировать общую стоимость всех цепей. Определите, существует ли какой-либо способ сделать ровно $$$m$$$ цепей, и, если да, выведите любое решение, которое минимизирует суммарную стоимость.

Входные данные

Во входных данных находятся несколько (не меньше одного) наборов входных данных. В первой строке находится одно целое число $$$T$$$ ($$$1 \le T \le 10$$$) — количество наборов входных данных. Далее следуют их описания.

Первая строка каждого набора содержит два целых числа $$$n$$$, $$$m$$$ ($$$2 \le n \le 1000$$$, $$$1 \le m \le n$$$) — количество людей, которые живут вместе с Ханьом и нужное количество цепей.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^4$$$) — цены холодильников.

Выходные данные

Для каждого набора выведите:

  • Если решение не существует, то выведите $$$-1$$$.
  • Иначе выведите $$$c$$$ — минимальную цену. Затем $$$i$$$-я из следующих $$$m$$$ строк должна содержать два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$), которые обозначают, что $$$i$$$-я цепь соединяет два холодильника $$$u_i$$$ и $$$v_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