题目背景

小明骑自行车去上学.....

题目描述

小明去上学的路是一条直线，直线上有 $n+1$ 个关键位置，其中第 $i$ 个关键位置距离家的长度为 $s_i$ ，其中第一个关键点是家，最后一个关键点是学校。保证 $s_i < s_{i+1}$ 。

小明的自行车是这样一个装置，自行车的向前的加速度最大为 $a$ ，但是刹车装置可以使速度瞬间降至 $0$ 或比当前速度低的任意值。同时，自行车的速度必须时刻保持速度 $v\geq 0$。现在他希望尽早的到达学校，不过由于关键点上有红绿灯或是宇宙射线等因素，小明必须在时间段 $[l_i,r_i]$ 中经过第 $i$ 个关键点，现在你需要通过规划自行车的加速和减速，使得小明在满足要求的情况下最早到达学校，如果无论如何都无法到达学校，请输出 "kaibai" （不包含引号）。

绝对误差或相对误差不超过 $10^{-4}$ 即算正确，保证对于无解的数据，即使将任意 $l_i,r_i$ 放大或者缩小 $0.001$ 倍仍然无解。

输入格式

$\begin{aligned} & n a \\ & s_1 s_2 \ldots s_{n+1} \\ & l_1 r_1 \\ & l_2 r_2 \\ & \ldots \\ & l_{n+1} r_{n+1}\end{aligned}$

输出格式

一行一个浮点数表示答案，请注意输出的小数点后位数达到了足够的精度。

4 2 
0 2 8 10 12 
0 1000000000 
2 2 
4 4 
6 7 
6 1000000000

6.5857864376

5 1 
0 1 2 3 4 5 
0 1000000000 
1 2 
2 3 
3 4 
4 5 
5 6

5.0000000000

数据约束

$1\leq n \leq 5000$

$1\leq a \leq 1000$

$0 = s_1 < s_2 < \dots < s_{n+1}\leq 10^9$

$l_1=0,r_1=10^9$ 和 $0\leq l_i \leq r_i \leq 10^9$

所有输入中的数均为自然数。

部分分

子任务1（30分）：保证 $n\leq10$。

子任务2（20分）：保证 $r_i=10^9$

子任务3（30分）：保证 $n\leq300$

子任务4（20分）：无额外限制。

尾声

感谢闫陈效 (chenxia25) 发现了题面以及数据里的 +∞ 个锅。

感谢程思元 (csy2005) 协助证明题解正确性。

[下发文件](file://attachment.zip) 这题有题解