Background

Xiao Ming is riding his bicycle to school...

Description

Xiao Ming's path to school is a straight line. There are $n+1$ key locations on this line. The $i$-th key location is at a distance $s_i$ from his home, where the first key location is his home and the last one is the school. It is guaranteed that $s_i < s_{i+1}$.

Xiao Ming's bicycle has a maximum forward acceleration of $a$. However, the braking system allows the speed to be instantly reduced to $0$ or any value lower than the current speed. Additionally, the bicycle's speed must always satisfy $v \geq 0$. He wants to reach the school as early as possible. Due to factors like traffic lights or cosmic rays at the key locations, Xiao Ming must pass the $i$-th key location within the time interval $[l_i, r_i]$. You need to plan the bicycle's acceleration and deceleration to ensure Xiao Ming reaches the school as early as possible while satisfying all requirements. If it is impossible to reach the school under any circumstances, output "kaibai" (without quotes).

An absolute or relative error of no more than $10^{-4}$ is considered correct. It is guaranteed that for cases with no solution, the problem remains unsolvable even if any $l_i, r_i$ are scaled by $0.001$.

Input

$$ \begin{align}\label{2} &n\ a & \\ &s_1\ s_2\ \dots \ s_{n+1} \\ &l_1\ r_1 \\ &l_2\ r_2 \\ &\dots \\ &l_{n+1}\ r_{n+1}\\ \end{align} $$

Output

Output a single floating-point number representing the answer. Please ensure the output has sufficient precision after the decimal point.

Examples

Input 1

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

Output 1

6.5857864376

Input 2

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

Output 2

5.0000000000

Constraints

$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$ and $0\leq l_i \leq r_i \leq 10^9$

All input numbers are natural numbers.

Subtasks

Subtask 1 (30 points): Guaranteed $n\leq 10$.

Subtask 2 (20 points): Guaranteed $r_i=10^9$.

Subtask 3 (30 points): Guaranteed $n\leq 300$.

Subtask 4 (20 points): No additional restrictions.

Note

Thanks to Yan Chenxiao (chenxia25) for discovering $+\infty$ bugs in the problem statement and data.

Thanks to Cheng Siyuan (csy2005) for assisting in proving the correctness of the solution.