#描述#
小R是一个典型的宅男，所以很自然地单身至今。作为他最好的朋友，你实在是看不下去了，于是给他安排了一系列的相亲活动。你给小R安排了N个女孩依次约会，但是你知道小R的情商非常低，他可能会和不合适的女孩一见钟情，不管以后会不会幸福就爱得死去活来；或者喜欢上一个根本不可能喜欢上他的女孩，然后自己纠结万分。为了避免这些情况的出现，你要故意给小R找点麻烦，使他错过某些约会。当然，你的目标是让他最后得到的幸福指数最高。
<BR>
<BR>

准确来说，现在有N个女孩，她们和小R约会的预定顺序已经不能更改了，如果没有意外的话，在接下来的N天里小R将依次与她们约会，每天约会一个。但是你有办法破坏掉其中的某些约会，使得那一天小R见不到本来该见的女孩。你已经计算出了小R和每个女孩成为情侣以后的幸福指数，你还计算出了小R爱上每个女孩的概率，以及每个女孩爱上小R的概率。请注意这两个事件是独立的，也就是说，设小R爱上女孩A的概率是p，女孩A爱上小R的概率是q，则他们彼此相爱成为情侣的概率是p*q，而小R陷入悲剧的单恋的概率是p*(1-q)。
<BR>
<BR>

你知道小R是一个非常专一的男孩，一旦他和某个女孩彼此相爱成为情侣，他就不再继续以后的约会了（尽管在你看来他们在一起可能并不太幸福）。你还知道如果小R爱上了某女孩但是女孩不喜欢他，他会难过K天，也就是说在接下来的K天里，即使有约会，他也不可能爱上任何女孩。当然，如果小R并没有爱上那个女孩，女孩的态度对他是没有影响的，他会继续下一天的约会。
<BR>
<BR>

当然你并不是神，你只能算出概率但不能保证结果，所以你只想安排出一个方案，使得小R得到的幸福指数的期望值最大。如果倒霉的小R到最后也没有和任何女孩成为情侣，他的幸福指数就是0。注意你的方案不是在一开始就完全确定，在每天的约会前你都可以根据以前的进展情况决定是否破坏掉这次的约会。

#格式#
##输入格式##
输入的第一行包含一个整数T (T ≤ 20)，表示共有T组数据。接下来每组数据的第一行是两个整数N和K (1 ≤ N ≤ 10^5, 0 ≤ K ≤ 10^5)，分别表示女孩的数目（呃，十万个女孩……）和小R被拒绝后的难过的天数。接下来N行，每行描述一个女孩。每行包含三个整数，分别表示小R爱上她的概率pi (0 ≤ pi ≤ 100)，她爱上小R的概率qi (0 ≤ qi ≤ 100)，以及他们成为情侣后的幸福指数hi (0 ≤ hi ≤ 10000)。概率均以百分之多少的形式表示。

##输出格式##
对每组数据输出一个数，表示经过你的安排后小R的期望幸福指数最大是多少。四舍五入到小数点后两位。

#样例1#
##样例输入1##

3

2 0
100 100 10
50 50 100

2 1
100 0 10000
50 100 100

2 0
100 90 1000
100 90 1000

##样例输出1##

25.00
50.00
990.00

#限制#
1000ms
32768KB

#提示#
第一组样例中，如果小R和第一个女孩约会，他们将百分之百地爱上对方，但是幸福指数只有10。所以你应该让小R错过第一场约会，这样他和第二个女孩将有25%的概率成为情侣，幸福指数为100，另外75%的概率小R仍然单身，幸福指数为0。则这种安排下期望的幸福指数为25%*100+75%*0 = 25
第二组样例中，如果小R和第一个女孩约会，他将一定爱上对方，但对方一定不爱她，这样小R会难过1天，导致不能爱上第二天的女孩。所以你应该让小R错过第一天约会，这样在第二天，他和第二个女孩有50%的概率成为情侣，幸福指数为100，另外50%的概率仍然单身，故期望的幸福指数为50
第三组样例中，你不应该进行任何干扰。小R有90%的概率和第一个女孩成为情侣，有10%*90%的概率和第二个女孩成为情侣，有10%*10%的概率最终仍单身，故期望幸福指数为90% * 1000 + 10% * 90% * 1000 + 10% * 10% * 0 = 990

#来源#
XTU