题目背景

小明骑自行车去上学……

题目描述

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

$$s_i<s_{i+1}.$$

小明的自行车具有如下特性：

• 自行车向前的最大加速度为 $a$；
• 刹车装置可以使速度瞬间降至 $0$，或降至任意一个不超过当前速度的值；
• 自行车的速度必须始终满足 $v\ge 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}$$

具体来说：

• 第一行包含两个整数 $n,a$；
• 第二行包含 $n+1$ 个整数 $s_1,s_2,\ldots,s_{n+1}$；
• 接下来 $n+1$ 行，第 $i$ 行包含两个整数 $l_i,r_i$。

输出格式

若有解，输出一行一个浮点数，表示小明最早到达学校的时间。请输出足够多的小数位以保证精度。

若无解，输出：

kaibai

样例 1

输入

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

输出

6.5857864376

样例 2

输入

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

输出

5.0000000000

数据范围

$$1\le n\le 5000$$ $$1\le a\le 1000$$ $$0=s_1<s_2<\cdots<s_{n+1}\le 10^9$$ $$l_1=0,\qquad r_1=10^9$$ $$0\le l_i\le r_i\le 10^9$$

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

部分分

• 子任务 1（30 分）：保证 $n\le 10$；
• 子任务 2（20 分）：保证 $r_i=10^9$；
• 子任务 3（30 分）：保证 $n\le 300$；
• 子任务 4（20 分）：无额外限制。