[NOI2012] 骑行川藏

题目描述

蛋蛋非常热衷于挑战自我,今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。 川藏线的沿途有着非常美丽的风景,但在这一路上也有着很多的艰难险阻,路况变化多端,而蛋蛋的体力十分有限,因此在每天的骑行前设定好目的地,同时合理分配好自己的体力是一件非常重要的事情。 由于蛋蛋装备了一辆非常好的自行车,因此在骑行过程中可以认为他仅在克服风阻做功(不受自行车本身摩擦力以及自行车与地面的摩擦力影响)。 某一天他打算骑 $n$ 段路,每一段内的路况可视为相同:对于第 $i$ 段路,我们给出有关这段路况的 $3$ 个参数 $s_i,k_i,v_i'$,其中 $s_i$ 表示这段路的长度,$k_i$ 表示这段路的风阻系数,$v_i'$ 表示这段路上的风速($v_i'\gt 0$ 表示在这段路上他遇到了顺风,反之则意味着他将受逆风影响)。 若某一时刻在这段路上骑车速度为 $v$,则他受到的风阻 大小为 $F=k_i(v-v_i')^2$(这样若在长度为 $s$ 的路程内保持骑行速度 $v$ 不变,则他消耗能量(做功)$E=k_i(v-v_i')^2s$ )。 设蛋蛋在这天开始时的体能值是 $E_U$,请帮助他设计一种行车方案,使他在有限的体力内用最短的时间到达目的地。请告诉他最短的时间 $T$ 是多少。

输入输出格式

输入格式


第一行包含一个正整数 $n$ 和一个实数 $E_U$,分别表示路段的数量以及蛋蛋的体能值。 接下来 $n$ 行分别描述 $n$ 个路段,每行有 $3$ 个实数 $s_i,k_i,v_i'$ 分别表示第 $i$ 段路的长度,风阻系数以及风速。

输出格式


输出一个实数 $T$,表示蛋蛋到达目的地消耗的最短时间,要求至少保留到小数点后 $6$ 位。

输入输出样例

输入样例 #1

3 10000
10000 10 5
20000 15 8
50000 5 6

输出样例 #1

12531.34496464

说明

### 样例说明 一种可能的方案是:蛋蛋在三段路上都采用匀速骑行的方式,其速度依次为 $5.12939919,8.03515481,6.17837967$。 ### 评分方法 本题没有部分分,你程序的输出只有和标准答案的差距不超过 $10^{-6}$ 时,才能获得该测试点的满分,否则不得分。 ### 数据规模与约定 对于 $10\%$ 的数据,$n=1$。 对于 $40\%$ 的数据,$n\le2$。 对于 $60\%$ 的数据,$n\le100$。 对于 $80\%$ 的数据,$n\le 1000$。 对于 $100\%$ 的数据,$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)$。 数据保证最终的答案不会超过 $10^5$。 ### 提示 必然存在一种最优的体力方案满足:蛋蛋在每段路上都采用匀速骑行的方式。