Discounts

题意翻译

## 题目描述 超市进行优惠活动，顾客如果在一架购物车中放上一个凳子，他就可以半价买掉这架购物车里最便宜的商品（一架购物车中只能让一个东西半价）。 现在$\mathrm{Polycarpus}$要用$k$架购物车（容量无限，但不能有空车）装要买的$n$件商品，里面有一些是凳子。$\mathrm{Polycarpus}$希望用最少的钱来买这些东西。 ## 输入格式 第一行两个整数$n$、$k$； 第$2$行至第$n+1$行，每行两个整数$c_i$、$t_i$，其中$c_i$表示商品$i$的价格，$t_i$表示类型（$1$表示它是凳子，$2$表示它不是凳子） ## 输出格式 第一行输出一个**一位小数**，表示折扣之后最少需要付的价格。 接下来的kkk行，每行开头输出一个整数$a_i$表示购物车$i$中商品的数量，后面跟着$a_i$个整数$b_1,b_2,...,b_j,...,b_{a_i}$表示商品的编号（$1\leq b_j\leq n$）。 方案可能有很多，输出其中一种即可。购物车和商品的输出顺序不作要求。 ### 说明/提示 在样例$1$中，购物车有$2$架，其中一架装商品$1$（凳子）和$2$（其他），另一架装商品$3$（凳子），这样安排便可以使价格最低。 对于$100\%$的数据，$1\leq n,k\leq 10^3$，$1\leq c_i\leq 10^9$，$1\leq t_i\leq 2$。

题目描述

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^{3} $ ) — 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^{9} $ ) 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.

输出格式

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.

输入输出样例

输入样例 #1

3 2
2 1
3 2
3 1

输出样例 #1

5.5
2 1 2
1 3

输入样例 #2

4 3
4 1
1 2
2 2
3 2

输出样例 #2

8.0
1 1
2 4 2
1 3

说明

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 $ .