Description

Dandan is very enthusiastic about challenging himself. This summer vacation he plans to ride a bicycle along the Sichuan–Tibet route from Chengdu to Lhasa.

The scenery along the Sichuan–Tibet route is beautiful, but there are many difficulties and changing road conditions along the way. Dandan’s stamina is limited, so before each day’s ride he sets a destination for the day and allocates his energy reasonably, which is very important.

Because Dandan is equipped with a very good bicycle, we can assume that during the ride he only does work to overcome air resistance (he is not affected by friction inside the bicycle or between the bicycle and the ground).

On a certain day he plans to ride $n$ segments. Within each segment the road condition can be considered uniform: for the $i$-th segment, we are given three parameters $s_i,k_i,v_i'$, where $s_i$ is the length of the segment, $k_i$ is the air-drag coefficient for the segment, and $v_i'$ is the wind speed on the segment ($v_i' \gt 0$ means tailwind on that segment; otherwise, it means headwind).

If at some moment his riding speed on this segment is $v$, then the magnitude of the air-drag force is $F=k_i(v-v_i')^2$ (therefore, if he maintains a constant speed $v$ over a distance $s$, he expends energy (does work) $E=k_i(v-v_i')^2s$).

Suppose Dandan’s energy budget at the start of the day is $E_U$. Please help him design a riding plan so that he reaches the destination in the shortest possible time within his energy budget. Please output the minimal time $T$.

Input Format

The first line contains a positive integer $n$ and a real number $E_U$, representing the number of segments and Dandan’s energy budget, respectively.

The next $n$ lines describe the $n$ segments. Each line contains three real numbers $s_i,k_i,v_i'$ representing the length, air-drag coefficient, and wind speed of the $i$-th segment.

Output Format

Output a real number $T$, the minimal time for Dandan to reach the destination. Keep at least $6$ digits after the decimal point.

3 10000
10000 10 5
20000 15 8
50000 5 6

12531.34496464

Hint

• Sample explanation: One possible plan is: Dandan rides at a constant speed on each of the three segments, with speeds $5.12939919, 8.03515481, 6.17837967$.

• Scoring: There are no partial scores. Your output must differ from the standard answer by no more than $10^{-6}$ to receive full score on a test point; otherwise you get zero for that point.

• Constraints: For $10\%$ of the testdata, $n=1$.

  For $40\%$ of the testdata, $n\le 2$.

  For $60\%$ of the testdata, $n\le 100$.

  For $80\%$ of the testdata, $n\le 1000$.

  For $100\%$ of the testdata, $n\le 10^4$, $E_U\le 10^8$, $s_i\in[0,10^5]$, $k_i\in(0,15]$, $v_i'\in(-100,100)$.

  The final answer is guaranteed not to exceed $10^5$.

• Additional hint: There always exists an optimal energy allocation in which Dandan rides at a constant speed on every segment.

Translated by ChatGPT 5