#643. hfz 的墙纸装修

hfz 的墙纸装修

说明


hfz 的房间刚刚装修完成,但是她发现之前在楼下堆放装修工具和建材的那面墙壁上的墙纸被蹭的破烂不堪,非常难看

作为一个完美主义者,hfz 想用装修剩下的木板暂时将这面墙壁给遮挡起来,等她买来新的墙纸,再来修复这面墙,巧合的是,装修剩下的 n 块木板居然全部都是三角形木板

hfz 测量了一下这面墙壁的宽度,发现长度是 L 而所有木板的高度都低于这面墙壁的高度,那就意味着如果只是把木板放在地上,是没有办法遮挡住整面墙壁的

hfz 想了各种办法,最后只能无奈的接受这个现实

但是她希望能用手里的这 n 块木板尽可能的遮挡住这面墙壁,而且既然没有办法遮住整面墙壁,索性破罐子破摔,也不去使用什么工具了,只是简单的将木板给贴墙放在地上

最终效果如下图所示


这些木板自然是可以重合的叠在一起,也可以有一部分超出墙壁的长度,但是最终 hfz 只想知道这些木板能遮住这面墙壁的最大面积是多少。

输入格式


输入第一行是一个整数 T,表示多组输入数据
对于每组输入数据:
输入第一行包含两个整数 n,L,含义如题
接下来 n 行每行包含三个正整数 a,b,c 分别表示每一块木板的三条边长

对于 10% 的数据,n <= 5

对于 30% 的数据,T <= 10, n <= 1000, L <= 10^5

对于 60% 的数据,T <= 10, n <= 10000, L <= 10^6

对于 100% 的数据,T <= 10, n <= 10^5, L <= 10^6, 0 < a_i <= b_i <= c_i <= 10^6

对于所有数据保证输入的 a_i^2 + b_i^2 >= c_i^2

输出格式

对于每组数据输出最多能被遮住的面积大小,答案四舍五入到小数点后三位。


样例

1
3 5
3 4 5
4 5 6
1 3 3
15.025