题目描述

你要买 $n$ 件物品，其中有一些是凳子。

商场正在举行促销活动，如果购物车中有至少一个凳子，那么你可以半价购买这个购物车中最贵的一个物品。

你有 $m$ 辆购物车，请最小化你的花费。

输入格式

第一行一个整数t表示数据组数 。

每组数据第一行两个整数 $n$ , $m$ ，接下来 $n$ 行每行两个整数 $a_i$ , $b_i$ ，分别表示第 $i$ 件物品的价格以及它是否是凳子 ( $1 ≤ a_i ≤ 10^5, 0 ≤ b_i ≤ 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

数据范围

对于 $100%$ 的数据，保证 $1 \le t \le 100,1 \le n,m \le 1000$ 。