CF161B.Discounts

One day Polycarpus stopped by a supermarket on his way home. It turns out that the supermarket is having a special offer for stools. The offer is as follows: if a customer's shopping cart contains at least one stool, the customer gets a 50% discount on the cheapest item in the cart (that is, it becomes two times cheaper). If there are several items with the same minimum price, the discount is available for only one of them!

Polycarpus has k carts, and he wants to buy up all stools and pencils from the supermarket. Help him distribute the stools and the pencils among the shopping carts, so that the items' total price (including the discounts) is the least possible.

Polycarpus must use all k carts to purchase the items, no shopping cart can remain empty. Each shopping cart can contain an arbitrary number of stools and/or pencils.

一天，波利卡普斯在回家途中顺道去了趟超市。结果发现，这家超市正在对凳子开展一项特别优惠活动。优惠规则如下：如果顾客的购物车中至少包含一把凳子，则该顾客可享受购物车中价格最低商品的 50% 折扣（即该商品价格变为原价的一半）。若存在多个价格相同的最低价商品，则仅其中一件可享受折扣！

波利卡普斯共有 $k$ 辆购物车，他希望买下超市中全部的凳子和铅笔。请你帮他将这些凳子和铅笔分配到各购物车中，使得所有商品的总价格（含折扣）最小。

波利卡普斯必须恰好使用全部 $k$ 辆购物车来购买这些商品，不允许有任何一辆购物车为空。每辆购物车可以装任意数量的凳子和/或铅笔。

The first input line contains two integers n and k (1 ≤ k ≤ n ≤ 103) — the number of items in the supermarket and the number of carts, correspondingly. Next n lines describe the items as "c__i t__i" (without the quotes), where c__i (1 ≤ c__i ≤ 109) is an integer denoting the price of the i-th item, t__i (1 ≤ t__i ≤ 2) is an integer representing the type of item i (1 for a stool and 2 for a pencil). The numbers in the lines are separated by single spaces.

第一行输入包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 10^3$），分别表示超市中商品的总数和购物车的数量。接下来的 $n$ 行描述了这些商品，每行为“$c_i\ t_i$”（不含引号），其中 $c_i$（$1 \le c_i \le 10^9$）为第 $i$ 个商品的价格（整数），$t_i$（$1 \le t_i \le 2$）为第 $i$ 个商品的类型（整数，1 表示凳子，2 表示铅笔）。每行中的数字以单个空格分隔。

In the first line print a single real number with exactly one decimal place — the minimum total price of the items, including the discounts.

In the following k lines print the descriptions of the items in the carts. In the i-th line print the description of the i-th cart as "t _b_1 _b_2 ... b__t" (without the quotes), where t is the number of items in the i-th cart, and the sequence _b_1, _b_2, ..., b__t (1 ≤ b__j ≤ n) gives the indices of items to put in this cart in the optimal distribution. All indices of items in all carts should be pairwise different, each item must belong to exactly one cart. You can print the items in carts and the carts themselves in any order. The items are numbered from 1 to n in the order in which they are specified in the input.

If there are multiple optimal distributions, you are allowed to print any of them.

第一行输出一个实数，精确到小数点后一位——即所有商品的最低总价（含折扣）。

接下来的 $k$ 行中，输出购物车中商品的描述。第 $i$ 行输出第 $i$ 个购物车的描述，格式为 “$t\ b_1\ b_2\ \dots\ b_t$”（不含引号），其中 $t$ 表示第 $i$ 个购物车中的商品数量，序列 $b_1,\ b_2,\ \dots,\ b_t$（满足 $1\le b_j\le n$）表示在最优分配方案中应放入该购物车的商品编号。所有购物车中商品编号两两不同，每个商品必须且仅属于一个购物车。购物车之间、以及各购物车内部商品的顺序可任意。商品按输入中给出的顺序编号为 $1$ 至 $n$。

若存在多个最优分配方案，输出其中任意一种即可。

In the first sample case the first cart should contain the 1st and 2nd items, and the second cart should contain the 3rd item. This way each cart has a stool and each cart has a 50% discount for the cheapest item. The total price of all items will be: 2·0.5 + (3 + 3·0.5) = 1 + 4.5 = 5.5.

在第一个样例中，第一辆购物车应包含第 1 和第 2 个商品，第二辆购物车应包含第 3 个商品。这样每辆购物车都有一张凳子，且每辆购物车中最便宜的商品均可享受 50% 的折扣。所有商品的总价格为：$2\cdot 0.5 + (3 + 3\cdot 0.5) = 1 + 4.5 = 5.5$。