F. Chemistry Lab
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

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}$$$.

Examples
Input
2 10
0 10 20
100 15 20
Output
175.000000000000000
Input
2 10
0 100 20
100 150 20
Output
0.000000000000000
Input
6 15
79 5 35
30 13 132
37 3 52
24 2 60
76 18 14
71 17 7
Output
680.125000000000000
Input
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
Output
2379.400000000000000