#2050. 「HEOI2015」小 L 的白日梦

「HEOI2015」小 L 的白日梦

说明

在某一天,你有了一个女性朋友。

你打算利用 kk 天时间陪她,每天有很多种娱乐方式可供选择,你需要从中选择一种进行(一天只能进行一个项目),比如说一起去看电影、一起去主题公园,一起去逛街等等,一共 nn 种项目。当然每个项目重复太多次你都会觉得无聊,因此第 ii 个项目最多进行 cic_i 次。你虽然智商很高,但是情商堪忧,即使这些你准备的活动都是希望让她开心的,不过由于你笨拙的语言表达和过于理智的行动,可能使这些活动出现意外。经过你悉心的计算,你发现如果某一天进行了第 ii 个项目,如果一切顺利的话她应该是很高兴的,但她会有 aia_i 的概率不高兴。如果她本来是很高兴的,但突然今天你让她不高兴了,她就会觉得很失落,并且对你的好感度大大下降。你希望尽可能避免这种情况发生,因此你要安排这 kk 天之内每天进行的项目,最小化她感到失落的期望次数。

你的女性朋友十分在意你,所以她的心情只会因为你发生改变。第一天之前,因为你没有邀请她进行任何活动,所以她是不高兴的。

输入格式

第一行有一个非负整数 tt,表示一共有 tt 组数据。

对于每组数据,第一行有两个非负整数 n,kn,k,分别表示你准备的项目个数和你用来陪她的天数。(n105, k109n \leq 10^5, \ k \leq 10^9

接下来 nn 行,每一行描述一个项目,形如xi/yi cix_i/y_i \ c_i且三个数均为非负整数,表示进行完这个项目之后她有 xi/yix_i/y_i 的概率不高兴,并且这个项目只能进行不超过 cic_i 次(xi,yi104, ci109x_i,y_i \leq 10^4, \ c_i \leq 10^9)。

输出格式

一共 tt 行,对于每组数据输出使她感到失落的最小期望次数,四舍五入保留六位小数。

样例

3
1 2
0/1 3
1 2
1/1 3
1 2
1/2 3
0.000000
0.000000
0.250000

考虑第三组数据,因为只有一个项目所以只好每天都安排这个。

在第一天之前她总是不高兴的,一共有:

  1. 第一天不高兴,第二天也不高兴;

  2. 第一天高兴,第二天不高兴;

  3. 第一天不高兴,第二天高兴;

  4. 第一天不高兴,第二天也不高兴。

这四种情况,又因为每天的项目让她高兴或者是不高兴的概率都是 0.50.5,因此这四种情况是等概率发生的。

只有在第二种情况下,她会感到失落一次。

因此答案是 1×1+0×34=0.25\frac{1 \times 1+0 \times 3}{4}=0.25

数据范围与提示

对于 100%100 \% 的数据,n105,k109n \leq 10^5, k \leq 10^9,数据组数不会太多,大概不超过十组,数据保证分数有意义并且 cik\sum c_i \geq k