Codeforces Round 601 (Div. 2) |
---|
Закончено |
Хань живет в общей квартире. Там живет $$$n$$$ человек (включая Ханя), у каждого из которых есть собственный холодильник.
$$$n$$$ холодильников защищены несколькими цепями. Каждая цепь соединяет два различных холодильника и защищена цифровым замком. Владелец холодильника знает коды доступа всех связанных с ним цепей. Холодильник может быть открыт только в том случае, если все цепи, подключенные к нему, разблокированы. Например, если холодильник вообще не имеет связанных с ним цепей, то его может открыть любой из $$$n$$$ человек.
Цены этих холодильников равны $$$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$$$) — цены холодильников.
Для каждого набора выведите:
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
Название |
---|