← 返回题目列表

Codeforces · 161/B

B. 折扣

中文机器翻译题面 查看原题

有一天,Polycarpus 在回家的路上经过一家超市。原来超市正在特价买凳子。优惠如下:如果顾客的购物车中至少包含一个凳子,则顾客购买购物车中最便宜的商品时可获得 50% 的折扣(即便宜两倍)。如果有多件商品的最低价格相同,则仅可享受其中一件折扣!

Polycarpus 有 k 辆购物车,他想从超市买下所有凳子和铅笔。帮助他在购物车中分配凳子和铅笔,使物品的总价(包括折扣)尽可能少。

Polycarpus 必须使用所有 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 进行编号。

如果有多个最优分布,则可以打印其中任何一个。

示例

输入 #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

注意

在第一个示例案例中,第一个购物车应包含第一个和第二个商品,第二个购物车应包含第三个商品。这样,每辆推车都有一个凳子,并且每辆推车对于最便宜的商品都有 50% 的折扣。所有商品的总价为:2·0.5 + (3 + 3·0.5) = 1 + 4.5 = 5.5。