Description

The way the automatic problem-solving machine works is very simple: it instantly figures out the correct solution to a problem, then starts writing code. Every second, the code generation module has two possible outcomes:

1. It writes $x$ lines of code.
2. In a bad mood, it deletes $y$ lines of previously written code. (If $y$ is greater than the current code length, this is equivalent to deleting everything.)

For an OJ, there is a fixed positive integer length $n$. Once the machine has accumulated at least $n$ lines of code at the end of a second, it will automatically submit and AC the problem, then create a new file (i.e., discard all previous code) and start the next problem. SHTSC ran the machine on an OJ for one day and obtained many log entries about code writing. He suddenly realized he did not record what $n$ on this OJ actually is. Fortunately, from his Rank on the OJ, he knows the machine solved $k$ problems in total. Please compute the minimum and maximum possible values of $n$.

Input Format

The first line contains two integers $l, k$, indicating that the machine produced $l$ log entries and solved $k$ problems in total.

The next $l$ lines each contain an integer $x_i$, describing each log entry in order. If $x_i \geq 0$, it means $x_i$ lines of code were written. If $x_i \lt 0$, it means $-x_i$ lines of code were deleted.

Output Format

Output one line with two integers, representing the minimum and maximum possible values of $n$.
If no such $n$ exists, output one line with a single integer $-1$.

4 2
2
5
-3
9

3 7

Hint

Constraints

• For $20\%$ of the testdata, it is guaranteed that $1 \le l \le 10$.
• For $40\%$ of the testdata, it is guaranteed that $1 \le l \le 100$.
• For $60\%$ of the testdata, it is guaranteed that $1 \le l \le 2 \times 10^3$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq l \le 10^5$, $-10^9 \le x_i \le 10^9$, and $k$ fits in the range of int.

Translated by ChatGPT 5