Как-то раз Поликарп по пути домой заглянул в супермаркет. Оказалось, что в супермаркете проходит акция по продаже табуреток. Условия акции таковы: если в корзинке с купленными товарами есть хотя бы одна табуретка, то на минимальный по стоимости товар из корзинки предоставляется скидка 50% (то есть он становится дешевле в два раза). Если товаров минимальной стоимости несколько, скидка предоставляется только на один из них!
У Поликарпа есть k корзинок, и он хочет скупить все табуретки и карандаши из супермаркета. Помогите ему распределить табуретки и карандаши по корзинкам так, чтобы суммарная стоимость товаров (с учетом скидок) была как можно меньше.
Поликарп обязан использовать все k корзинок для покупки товаров, ни одна корзинка не должна остаться пустой. В каждой корзинке может быть произвольное количество табуреток и/или карандашей.
Выходные данные
В первую строку выведите единственное вещественное число с ровно одним знаком после запятой — минимальную суммарную стоимость товаров с учетом скидок.
В следующих k строках выведите описания товаров в корзинках. В i-й строке выведите описание i-й корзинки в формате «t b1 b2 ... bt» (без кавычек), где t — количество товаров в i-й корзинке, а последовательность b1, b2, ..., bt (1 ≤ bj ≤ n) — номера товаров, которые следует положить в эту корзинку в оптимальном распределении. Все номера товаров во всех корзинках должны быть попарно различны, каждый товар должен находиться ровно в одной корзинке. Товары в корзинках и сами корзинки можно выводить в любом порядке. Товары нумеруются от 1 до n в том порядке, в котором они заданы во входных данных.
Если существует несколько оптимальных распределений, разрешается вывести любое.
Примечание
В первом примере в первую корзинку следует положить 1-ый и 2-ой товар, а во вторую — 3-ий товар. Тогда в каждой корзинке будет табуретка, и на товар минимальной стоимости предоставляется скидка 50%. Суммарная стоимость товаров составит: 2·0.5 + (3 + 3·0.5) = 1 + 4.5 = 5.5.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
2 1
3 2
3 1
|
5.5
2 1 2
1 3
|
|
2
|
4 3
4 1
1 2
2 2
3 2
|
8.0
1 1
2 4 2
1 3
|