你准备到商店利购物，你发现有不少物品捆绑了优惠券，如果购买了这个捆绑了优惠券的物品，那么你可以将你购物车里某个物品半价购买，现在有你买了N件物品和用了M两购物车，请你问最小花费是多少？

第一行一个整数t表示数据组数 (1 ≤ t ≤ 100)。 每组数据第一行两个整数n,m (1 ≤ n,m ≤ 1000)，接下来n行每行两个整数ai,bi，分别表示第i件物品的价格以及它是否是凳子 (1 ≤ ai ≤ 10^5, 0 ≤ bi ≤ 1)。

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