#NC19784. Shopping

Shopping

题目描述

你要买n件物品,其中有一些是凳子。 商场正在举行促销活动,如果购物车中有至少一个凳子,那么你可以半价购买这个购物车中最贵的一个物品。 你有m辆购物车,请最小化你的花费。

输入格式

第一行一个整数t表示数据组数 (1 ≤ t ≤ 100)。 每组数据第一行两个整数 n,mn,m,其中 1≤n,m≤10001\leq n,m\leq1000。

接下来 nn 行,每行两个整数 ai,bia_i,b_i,分别表示第 ii 件物品的价格以及它是否是凳子,其中 1≤ai≤1051\leq a_i\leq10^5,bi∈{0,1}b_i\in\{0,1\}。bi=1b_i=1 表示该物品是凳子,bi=0b_i=0 表示不是。

输出格式

每组数据输出一行一个实数表示最小花费,保留一位小数。

样例 1

2
5 1
1 0
2 1
3 1
4 0
5 0
5 10
1 0
2 1
3 1
4 0
5 0
12.5
10.5

来源

牛客原题