B. Скидки
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Как-то раз Поликарп по пути домой заглянул в супермаркет. Оказалось, что в супермаркете проходит акция по продаже табуреток. Условия акции таковы: если в корзинке с купленными товарами есть хотя бы одна табуретка, то на минимальный по стоимости товар из корзинки предоставляется скидка 50% (то есть он становится дешевле в два раза). Если товаров минимальной стоимости несколько, скидка предоставляется только на один из них!

У Поликарпа есть k корзинок, и он хочет скупить все табуретки и карандаши из супермаркета. Помогите ему распределить табуретки и карандаши по корзинкам так, чтобы суммарная стоимость товаров (с учетом скидок) была как можно меньше.

Поликарп обязан использовать все k корзинок для покупки товаров, ни одна корзинка не должна остаться пустой. В каждой корзинке может быть произвольное количество табуреток и/или карандашей.

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

В первой строке входных данных записано два целых числа n и k (1 ≤ k ≤ n ≤ 103) — количество товаров в супермаркете и количество корзинок у Поликарпа, соответственно. В следующих n строках заданы описания товаров в виде «ci ti» (без кавычек), где ci (1 ≤ ci ≤ 109) — целое число, обозначающее стоимость i-го товара, ti (1 ≤ ti ≤ 2) — целое число, обозначающее тип i-го товара (1 — табуретка, 2 — карандаш). Числа в строках разделяются одним пробелом.

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

В первую строку выведите единственное вещественное число с ровно одним знаком после запятой — минимальную суммарную стоимость товаров с учетом скидок.

В следующих k строках выведите описания товаров в корзинках. В i-й строке выведите описание i-й корзинки в формате «t b1 b2 ... bt» (без кавычек), где t — количество товаров в i-й корзинке, а последовательность b1, b2, ..., bt (1 ≤ bj ≤ n) — номера товаров, которые следует положить в эту корзинку в оптимальном распределении. Все номера товаров во всех корзинках должны быть попарно различны, каждый товар должен находиться ровно в одной корзинке. Товары в корзинках и сами корзинки можно выводить в любом порядке. Товары нумеруются от 1 до n в том порядке, в котором они заданы во входных данных.

Если существует несколько оптимальных распределений, разрешается вывести любое.

Примеры
Входные данные
3 2
2 1
3 2
3 1
Выходные данные
5.5
2 1 2
1 3
Входные данные
4 3
4 1
1 2
2 2
3 2
Выходные данные
8.0
1 1
2 4 2
1 3
Примечание

В первом примере в первую корзинку следует положить 1-ый и 2-ой товар, а во вторую — 3-ий товар. Тогда в каждой корзинке будет табуретка, и на товар минимальной стоимости предоставляется скидка 50%. Суммарная стоимость товаров составит: 2·0.5 + (3 + 3·0.5) = 1 + 4.5 = 5.5.