Discounts

Description:

Input:

The first input line contains two integers n and k (1 ≤ k ≤ n ≤ 10³) — 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 ≤ 10⁹) 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.

Output:

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₁ b₂ ... b_t" (without the quotes), where t is the number of items in the i-th cart, and the sequence b₁, b₂, ..., 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.

Sample Input:

3 2
2 1
3 2
3 1

Sample Output:

5.5
2 1 2
1 3

Sample Input:

4 3
4 1
1 2
2 2
3 2

Sample Output:

8.0
1 1
2 4 2
1 3

Note:

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.