Chemistry Lab
Contest: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2200
Tags: dp, geometry, probabilities

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
2 10
0 10 20
100 15 20

Example output:
175.000000000000000

Example input:
2 10
0 100 20
100 150 20

Example output:
0.000000000000000

Editorial:
Let's start without picking the contracts. Buy them all and at least learn to calculate the answer.
Obviously, $$$k$$$ doesn't really matter for the answer. Linearity of expectation, it will be just something multiplied by $$$k$$$.
Imagine there's just one contract. Since we can't really mix it with anything, and the probability that the customer picks exactly that concentration is $$$0$$$, the answer is $$$0$$$.
What about two contracts? If you draw them as points $$$(x_i, c_i)$$$ on the grid, then all solutions, that can be obtained from a mix of them, are a segment. Basically, the formula is exactly the parametric equation for the segment, and that's how you could come to this conclusion. The expected cost is some integral, which is basically an area below the segment.
Three contracts? As a reasonable conclusion, now it's a triangle on these points. To show that, let's fix one of these points $$$A$$$, opposite to some base of the triangle $$$BC$$$. Pick a percentage of the solution $$$A$$$, then draw a segment from $$$A$$$ to that percentage of $$$BC$$$. If you fix the percentages of $$$B$$$ and $$$C$$$ (the point on the segment $$$BC$$$), then you can basically continuously gravitate this point towards $$$A$$$ along the drawn segment by increasing the concentration of $$$A$$$ and decreasing the concentrations of $$$B$$$ and $$$C$$$, while keeping their proportion to each other the same. The union of all options covers the entire triangle and can never go outside it.
Ok, let's make an educated guess about more contracts and try to show that. All solutions, that can be obtained with a mix of several solutions, are insides of a convex hull of the set of points. Let the set of points be convex already. If it isn't, we can say that the answer is the union of all convex subsets of it, which is equal to the convex hull. To prove it for the convex set, we can choose any three consecutive points on it and contract them into a segment, with the proof for the triangle. Continue until we reach two points.
All solutions are a convex hull, but we only care about the ones with the maximum cost. That would be the set of the highest intersection points of the convex hull and the vertical lines for all concentrations. Which is known as an upper envelope of the convex hull. The expected cost is the area below that upper envelope.
So we learned to calculate the answer for a fixed set of solutions. Let's learn how to pick them.
We want to directly construct that upper envelope. Let me first tell you a direct but a slow solution.
Do dynamic programming. Sort the solutions first in the increasing order of their concentration, second in the increasing order of their cost per litre. Now do $$$dp[i][j]$$$ — the maximum answer if the last point in the upper envelope is $$$j$$$ and the second last is $$$i$$$. To transition, iterate over the next point $$$k$$$ in that upper envelope and check if the triple $$$(i, j, k)$$$ is clockwise. To update the answer, add the newly added area below the segment $$$(j, k)$$$, which is a trapezoid, multiplied by $$$k$$$, and subtract the cost of the contract $$$k$$$. That would be $$$O(n^3)$$$.
Now for the funny transition. Basically, we can just not care that the points we pick give us an upper envelope. If we picked a set of points, which is not convex, then we can safely remove some points (pay less money for the contracts) and our calculated area can never decrease from that (since we still are picking points in the increasing order of $$$x$$$ and $$$y$$$).
Thus, we can remove the second to last point in the dp and only store the last one. That is enough to recalculate the area.
Overall complexity: $$$O(n^2)$$$.