P2497 [SDOI2012] Base Station Construction

The uploader (UP 主) finally bought a computer, but now there are various issues to deal with. The first problem to solve is the network. He wants to start from the mobile company and relay the network to his home through some base stations. To simplify the problem, we assume the mobile company, all base stations, and the UP's home lie on the same straight line, each located at some point $x$ on this line. These points may coincide. Each base station’s transmit and receive ranges are circles tangent to the ground. The transmit radius $r$ is fixed, while the receive radius $r'$ is adjustable. See the figure:  If base station $i$ wants to receive a signal from another base station $j$ (if and only if $x_j < x_i$), it must satisfy that $i$’s receive range is tangent to $j$’s transmit range, and an extra cost of $\sqrt{r'_i}$ must be paid. Activating each point $i$ costs $v_i$. For the UP’s home to receive a signal from some base station, it suffices that this station’s transmit range is tangent to or intersects the vertical line passing through the UP’s home, as shown below:  Of course, the smaller the total cost, the better, so the UP wants your help.

The first line contains two integers $n, m$: the number of base stations (including the mobile company), and the coordinate of the UP’s home. It is guaranteed that $m$ is greater than or equal to the coordinates of all base stations. The next $n$ lines each contain three integers $x_i$, $r_i$, $v_i$, representing the coordinate, transmit radius, and activation cost of each base station. The $x_i$ are given in increasing order of coordinates, and the mobile company is at the smallest coordinate. The sequence $\{r_i\}$ is a permutation of $1 \dots n$.

Output a real number with exactly three digits after the decimal point.

For $100\%$ of the testdata, $n \le 5 \times 10^5$, $x_i, m \le 10^{12}$, $v_i \le 10000$. Translated by ChatGPT 5