P6863 [RC-03] Seeking Up and Down

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.

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 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).

[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_116$. 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