Description

There is an $n$-variable quadratic equation about $x_i(i∈\{1,2,3,...,n\},x_i∈\mathbb{R})$:

$$\sum_{i=1}^na_ix_i^2+\sum_{i=1}^{n-1}b_ix_ix_{i+1}=m$$

In this equation, please find the range of values of $x_1$ that guarantees the equation has at least one solution.

It is guaranteed that $x_1$ has both a lower bound and an upper bound.

Input Format

The input has three lines.

The first line contains two integers $n,m$.

The second line contains $n$ integers $a_i$, where $i∈\{1,2,3,..,n\}$.

The third line contains $n-1$ integers $b_i$, where $i∈\{1,2,3,..,n-1\}$.

Output Format

Output one line with two integers separated by a space, representing the lower bound and upper bound of $x_1$ (it is guaranteed that the output is always integers).

5 16
2 2 2 2 1
2 2 2 2

-4 4

Hint

[Sample $1$ Explanation]

The original equation is $2x_1^2+2x_1x_2+2x_2^2+2x_2x_3+2x_3^2+2x_3x_4+2x_4^2+2x_4x_5+x_5^2=16$.

When $x_1=-4$, we have $x_1=-4$; $x_2=4$; $x_3=-4$; $x_4=4$; $x_5=-4$.
When $x_1=4$, we have $x_1=4$; $x_2=-4$; $x_3=4$; $x_4=-4$; $x_5=4$.
When $x_1>4$ or $x_1<-4$, the left-hand side of the original equation must be $>16$.
Therefore, $-4\leq x_1\leq 4$.

---

[Constraints]

For $4\%$ of the testdata, $n=1$.

For $16\%$ of the testdata, $n\le 2$.

For another $16\%$ of the testdata, $n\le 8$, $m\le 30$.

For $60\%$ of the testdata, $n\le 10^3$.

For $100\%$ of the testdata, $1\le a_i,b_i,m\leq 10^9$, $1\le n\leq 5\times 10^5$.

Translated by ChatGPT 5