#P3006. 基站建设

基站建设

基站建设 [废题]

题目描述

Up 主想让移动公司的网络通过若干基站传到家里。移动公司、各基站和 Up 主家都在同一条水平直线上。各基站的坐标互不相同。

每个基站的发射范围是一个与地面相切的圆,圆在地面上的切点就是该基站的位置。发射半径 r1r_1 固定。接收范围也是一个在该点与地面相切的圆,接收半径 r2r_2 可以调整。

同一基站固定的发射半径和可调的接收半径

基站 ii 可以接收位于它左侧的基站 jj 的信号。当且仅当基站 ii 的接收圆与基站 jj 的发射圆外切时,可以通过这两个基站传递信号。接收所用的半径为 r2r_2 时,要额外支付 r2\sqrt{r_2} 的费用。启用基站 ii 还须支付费用 viv_i。

移动公司位于最左侧,也算一个基站。接到网络信号的基站可以转发。若该基站的发射圆与经过 Up 主家的竖线相切或相交,信号就可到达 Up 主家。

发射圆和 Up 主家所在的竖线相交

求使信号从移动公司传到 Up 主家的最少费用。

输入格式

第一行两个整数 n,mn,m,分别为基站总数(包括移动公司)和 Up 主家所在坐标。mm 不小于任何基站坐标。

接下来 nn 行,每行三个整数 xi,r1,i,vix_i,r_{1,i},v_i,表示基站位置、发射圆半径与启用费用。基站依 xix_i 严格递增。发射半径是 1,…,n1,\ldots,n 的一个排列。

原题给定 n≤5×106n\le5\times10^6、xi,m≤1012x_i,m\le10^{12}、vi≤104v_i\le10^4。

输出格式

输出一行一个实数,表示最少费用,保留小数点后三位。

样例

10 33
5 4 660
10 2 2040
11 6 3207
14 5 2006
18 3 6130
19 9 3363
22 1 1265
25 8 2836
27 10 7961
29 7 9075
3501.000