Monocarp 计划开设一个化学实验室。在第一个月,他将分发某种酸的溶液。
首先,他将与当地一家化工厂签订一些合同。每份合同都为 Monocarp 提供无限量的相同酸溶液的供应。工厂提供$$$n$$$合约选项,编号从$$$1$$$到$$$n$$$。第 $$$i$$$ 溶液的浓度为 $$$x_i\%$$$,合同成本为 $$$w_i$$$ 糖节,Monocarp 能够以每升 $$$c_i$$$ 糖节的价格出售。
Monocarp 在第一个月预计会有 $$$k$$$ 客户。每个客户将购买一升 $$$y\%$$$ 溶液,其中 $$$y$$$ 是为每个客户独立从 $$$0$$$ 到 $$$100$$$ 均匀随机选择的实数。更正式地说,数字 $$$y$$$ 小于或等于某个 $$$t$$$ 的概率为 $$$P(y \le t) = \frac{t}{100}$$$。
Monocarp可以以任意比例混合他与工厂签订的合同中的解决方案。更正式地说,如果他签订了 $$$m$$$ 溶液浓度 $$$x_1, x_2, \dots, x_m$$$ 的合同,那么,对于这些溶液,他选择其体积 $$$a_1, a_2, \dots, a_m$$$ 以便 $$$\sum \limits_{i=1}^{m} a_i = 1$$$ (确切地说是 $$$1$$$,因为每个客户都想要确切的值)一升某种溶液)。
所得溶液的浓度为 $$$\sum \limits_{i=1}^{m} x_i \cdot a_i$$$。所得解决方案的价格为 $$$\sum \limits_{i=1}^{m} c_i \cdot a_i$$$。
如果 Monocarp 可以获得浓度 $$$y\%$$$ 的溶液,那么他会在最大化其价格(客户的成本)的同时做到这一点。否则,顾客没有购买任何东西就离开,并且价格被认为等于$$$0$$$。
Monocarp 希望与工厂签订一些合同(可能不签订或全部签订),以便实现预期利润最大化 - 所有 $$$k$$$ 客户的已售解决方案的预期总价减去与工厂签订合同的总成本。
打印 Monocarp 可以实现的最大预期利润。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 5000$$$; $$$1 \le k \le 10^5$$$)——工厂提供的合同数量和客户数量。
接下来的 $$$n$$$ 行的第 $$$i$$$ 包含三个整数 $$$x_i、w_i$$$ 和 $$$c_i$$$ ($$$0 \le x_i \le 100$$$; $$$1 \le w_i \le 10^9$$$; $$$1 \le c_i \le 10^5$$$) — 第 $$$i$$$ 合同的溶液浓度、合同成本以及客户每升的成本。
输出
打印单个实数 - Monocarp 可以实现的最大预期利润。
如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。
示例
输入 #1
2 10 0 10 20 100 15 20
输出 #1
175.000000000000000
输入 #2
2 10 0 100 20 100 150 20
输出 #2
0.000000000000000
输入 #3
6 15 79 5 35 30 13 132 37 3 52 24 2 60 76 18 14 71 17 7
输出 #3
680.125000000000000
输入#4
10 15 46 11 11 4 12 170 69 2 130 2 8 72 82 7 117 100 5 154 38 9 146 97 1 132 0 12 82 53 1 144
输出#4
2379.400000000000000