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.
The first input line contains two integers *n* and *k* (1 ≤ *k* ≤ *n* ≤ 10<sup class="upper-index">3</sup>) — the number of items in the supermarket and the number of carts, correspondingly. Next *n* lines describe the items as "*c*<sub class="lower-index">*i*</sub> *t*<sub class="lower-index">*i*</sub>" (without the quotes), where *c*<sub class="lower-index">*i*</sub> (1 ≤ *c*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) is an integer denoting the price of the *i*-th item, *t*<sub class="lower-index">*i*</sub> (1 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 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.
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
1 2
2 3 4
1 1
1 1
0.5
1 1
1 1
1 2
1.0
1 1
10 1
1 1
2 2
1 1
23 2
17 2
1 1
1 1
30 2
1 1
9 2
85.5
10 1 2 4 5 8 10 3 6 7 9
11 11
6 2
6 2
1 2
2 2
3 1
6 2
1 1
1 1
3 1
3 1
6 2
32.5
1 5
1 9
1 10
1 7
1 8
1 1
1 2
1 3
1 4
1 6
1 11
5 4
24 1
19 1
28 2
7 1
23 2
76.0
1 1
1 2
1 4
2 3 5
20 3
28 1
786180179 2
16 1
617105650 2
23 1
21 1
22 1
7 1
314215182 2
409797301 2
14 1
993310357 2
372545570 2
791297014 2
13 1
25 1
307921408 2
625842662 2
136238241 2
13 1
5354453716.0
18 5 2 4 9 10 12 13 14 17 18 19 7 6 3 11 15 20 8
1 1
1 16
21 7
14 1
882797755 2
17 1
906492329 2
209923513 2
802927469 2
949195463 2
677323647 2
2129083 2
2 1
13 1
539523264 2
7 1
8 1
12 1
363470241 2
9838294 2
18716193 2
30 1
17 1
24 1
5362337336.5
15 15 2 4 5 6 7 8 9 12 16 17 18 14 13 10
1 19
1 21
1 3
1 20
1 1
1 11
21 21
42856481 2
562905883 2
942536731 2
206667673 2
451074408 2
27 1
29 1
172761267 2
23 1
24 1
106235116 2
126463249 2
29 1
9 1
83859496 2
5 1
25 1
337838080 2
109402491 2
5 1
24 1
3142600975.0
1 7
1 13
1 6
1 17
1 10
1 21
1 9
1 14
1 16
1 20
1 1
1 2
1 3
1 4
1 5
1 8
1 11
1 12
1 15
1 18
1 19
10 1
28 1
1 2
1 2
1 2
15 1
16 1
22 1
20 1
1 2
1 2
105.5
10 1 2 3 4 9 10 7 8 6 5
5 4
10 1
10 1
10 1
9 1
5 2
26.5
2 4 5
1 1
1 2
1 3
7 4
10 1
10 1
10 1
9 1
2 1
5 2
3 2
33.0
4 4 6 7 5
1 1
1 2
1 3
7 4
10 1
10 1
10 1
9 1
4 1
5 2
3 2
34.5
4 4 6 7 5
1 1
1 2
1 3
7 5
10 1
10 1
10 1
9 1
4 1
5 2
3 2
30.0
3 5 6 7
1 1
1 2
1 3
1 4
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1005;

int n, k;
int c[N], t[N];
vector<pair<int, int> > s, p;//price, index value of stool,pencil
double ans = 0;
bool vis[N];

signed main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> c[i] >> t[i];
		if (t[i] == 1)
			s.push_back({c[i], i});
		else
		{
			p.push_back({c[i], i});
			ans += c[i];//adding price to our answer
		}
	}
	sort(s.rbegin(), s.rend());//sorting stools in reverse order of price(decresing order)
	vector<int> v;
	//adding most expensive stools in our cart and halving their price
	for (int i = 0; i < s.size(); i++)
	{
		//adding only most expensive stools in k-1 carts and halving their price
		//and marking them visited
		if (i <= k - 2)
		{
			ans += 0.5 * s[i].first;
			vis[s[i].second] = 1;
		}
		//adding all other in last cart
		else
			ans += s[i].first;
	}
	double mn = 1e9;
	for (int i = 1; i <= n; i++)
	{
		if (!vis[i]) //calculating the minimum of all nonvisted stools and pencils
			mn = min(mn, 1.0 * c[i]);
	}
	//decresing the minimum of all nonvisted stools and pencils which are in last cart by 50%
	//if only stools are greater then carts because we need 1 stool in each kart for discount
	if (s.size() >= k)
		ans -= 0.5 * mn;
	//printing our final bill amount
	cout << fixed << setprecision(1) << ans << endl;
	//printing all the index  which are in carts
	//such that each discounted cart has 1 stool which is most expensive in the cart and all
	//other in last cart
	int printed = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if (i <= k - 2)
		{
			printed++;
			cout << 1 << " " << s[i].second << endl;
		}
	}
	vector<int> rem;
	for (int i = 1; i <= n; i++)
	{
		if (!vis[i])
			rem.push_back(i);
	}
	while (printed + 1 < k)
	{
		cout << 1 << " " << rem.back() << endl;
		rem.pop_back();
		printed++;
	}
	cout << rem.size() << " ";
	for (auto &it : rem)
		cout << it << " ";
	return 0;
}