题目描述

我们已经学过了基于动态规划的0-1背包算法，即用状态\(f[x][u]\)表示用前\(x\)件物品填充容量限制为\(u\)的子背包，最多可以产生多少价值。但动态规划算法只局限于\(u\)的范围较小，且均为非负整数的情形。显然当\(u\)为浮点数时，这种动态规划解法就不再适用了。
本题就是每件物品重量、价值均为浮点数的0-1背包问题。

输入格式

输入第一行是一个正整数\(T\)，表示测试数据组数。之后每组数据：
第一行是一个正整数\(N\)，表示物品的件数；然后是一个浮点数\(W\)，表示背包的总容量；
之后\(N\)行，每行两个浮点数\(w_i, v_i\)，分别表示该件物品的重量与价值。
所有浮点数均保留至多3位小数。

输出格式

每组数据输出一行，在选取物品的总重量不超过\(W\)的前提下，总价值最多可以是多少，四舍五入保留3位小数。

样例

输入

2
3 10.0
3.5 1.75
4.0 3.2
6.4 3.25
4 10.0
3.5 150.01
2.5 80.02
6.1 450.04
4.1 320.08

输出

5.000
600.050

数据规模及约定

\(T \le 10, \quad N \le 20, \quad 0.0 < W < 10^5, \quad 0.0 < w_i < W, \quad 0.0 < v_i < 10^5\)
为了避免浮点数精度误差带来的影响，保证对于所有物品的任意一个子集，\(\lvert \sum w_i - W \rvert > 10^{-3}\)
数据已大幅加强
时间限制1s，空间限制64MB。