CF1765F.Chemistry Lab

Monocarp is planning on opening a chemistry lab. During the first month, he's going to distribute solutions of a certain acid.

First, he will sign some contracts with a local chemistry factory. Each contract provides Monocarp with an unlimited supply of some solution of the same acid. The factory provides $n$ contract options, numbered from $1$ to $n$. The $i$-th solution has a concentration of $x_i\%$, the contract costs $w_i$ burles, and Monocarp will be able to sell it for $c_i$ burles per liter.

Monocarp is expecting $k$ customers during the first month. Each customer will buy a liter of a $y\%$-solution, where $y$ is a real number chosen uniformly at random from $0$ to $100$ independently for each customer. More formally, the probability of number $y$ being less than or equal to some $t$ is $P(y \le t) = \frac{t}{100}$.

Monocarp can mix the solution that he signed the contracts with the factory for, at any ratio. More formally, if he has contracts for $m$ solutions with concentrations $x_1, x_2, \dots, x_m$, then, for these solutions, he picks their volumes $a_1, a_2, \dots, a_m$ so that $\sum \limits_{i=1}^{m} a_i = 1$ (exactly $1$ since each customer wants exactly one liter of a certain solution).

The concentration of the resulting solution is $\sum \limits_{i=1}^{m} x_i \cdot a_i$. The price of the resulting solution is $\sum \limits_{i=1}^{m} c_i \cdot a_i$.

If Monocarp can obtain a solution of concentration $y\%$, then he will do it while maximizing its price (the cost for the customer). Otherwise, the customer leaves without buying anything, and the price is considered equal to $0$.

Monocarp wants to sign some contracts with a factory (possibly, none or all of them) so that the expected profit is maximized — the expected total price of the sold solutions for all $k$ customers minus the total cost of signing the contracts from the factory.

Print the maximum expected profit Monocarp can achieve.

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$（因为每位顾客恰好需要一升特定浓度的溶液）。

所得混合溶液的浓度为 $\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 能达到的最大期望利润。

The first line contains two integers $n$ and $k$ ($1 \le n \le 5000$; $1 \le k \le 10^5$) — the number of contracts the factory provides and the number of customers.

The $i$-th of the next $n$ lines contains three integers $x_i, w_i$ and $c_i$ ($0 \le x_i \le 100$; $1 \le w_i \le 10^9$; $1 \le c_i \le 10^5$) — the concentration of the solution, the cost of the contract and the cost per liter for the customer, for the $i$-th contract.

第一行包含两个整数 $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$ 个合同对应溶液的浓度、该合同的成本，以及该客户每升溶液所需支付的费用。

Print a single real number — the maximum expected profit Monocarp can achieve.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$.

输出一个实数——Monocarp 能够获得的最大期望利润。

若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

形式化地，设你的答案为 $a$，评测系统的答案为 $b$。当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$ 时，你的答案被接受。