Comet OJ

C1533 [NOI2012]骑行川藏

内存限制：512 MB 时间限制：1000 ms

题目描述

蛋蛋非常热衷于挑战自我，今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。川藏线的沿途有着非常美丽的风景，但在这一路上也有着很多的艰难险阻，路况变化多端，而蛋蛋的体力十分有限，因此在每天的骑行前设定好目的地、同时合理分配好自己的体力是一件非常重要的事情。

由于蛋蛋装备了一辆非常好的自行车，因此在骑行过程中可以认为他仅在克服风阻做功（不受自行车本身摩擦力以及自行车与地面的摩擦力影响）。某一天他打算骑 $N$ 段路，每一段内的路况可视为相同：对于第 $i$ 段路，我们给出有关这段路况的 $3$ 个参数 $s_i,k_i,v_i$，其中 $s_i$ 表示这段路的长度，$k_i$ 表示这段路的风阻系数，$v_i$ 表示这段路上的风速（$v_i>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$。

【评分方法】

你程序的输出只有和标准答案的差距不超过 $0.000001$ 时，才能获得该测试点的满分，否则不得分。

【数据规模与约定】

对于 $10\%$ 的数据，$N = 1$；

对于 $40\%$ 的数据，$N ≤ 2$；

对于 $60\%$ 的数据，$N ≤ 100$；

对于 $80\%$ 的数据，$N ≤ 1000$；

对于所有数据，$N ≤ 10000,0 ≤ E_U≤ 10^8，0 < s_i≤ 100000，0 < k_i≤ 15，−100 < v_i< 100$。数据保证最终的答案不会超过 $10^5$。

【提示】

必然存在一种最优的体力方案满足：蛋蛋在每段路上都采用匀速骑行的方式。