The inventor SHTSC, who once invented a signal amplifier, has unveiled his new invention: the Automatic Problem-Solving Machine—a mysterious device that can automatically AC (solve) problems.

The way the Automatic Problem-Solving Machine works is very simple: it instantly determines the correct approach to a problem and then begins writing the program. Every second, the machine's code generation module produces one of two possible results:

A. It writes $x$ lines of code. B. It is in a bad mood and deletes $y$ lines of previously written code. (If $y$ is greater than the current number of lines of code, it is equivalent to deleting all of them.)

For every problem on an OJ, there exists a fixed length $n > 0$. Once the machine has accumulated $n$ or more lines of code at the end of any given second, it automatically submits the code, ACs the problem, and starts a new file to begin working on the next problem.

SHTSC ran the Automatic Problem-Solving Machine on an OJ for a day and obtained many log entries regarding the code writing process. He suddenly realized that he had not recorded what the value of $n$ for this OJ was. Fortunately, he knows from his rank on the OJ that the machine solved a total of $k$ problems. You are asked to calculate the minimum and maximum possible values of $n$.

Input

The first line contains two integers $l$ and $k$, representing that the machine's log has $l$ lines and it solved a total of $k$ problems.

The second line contains $l$ integers $x_1, \dots, x_l$. If $x_i \ge 0$, it means the machine wrote $x_i$ lines of code. If $x_i < 0$, it means the machine deleted $-x_i$ lines of code.

Output

Output two integers $a$ and $b$, representing the minimum and maximum possible values of $n$, respectively. If no such $n$ exists, output -1.

Constraints

For 20% of the data: $\sum |x_i| \le 2000$. For 60% of the data: $l \le 2000, k \le 100$. For 100% of the data: $1 \le l, k \le 100000, |x_i| \le 10^9$.

Examples

Input 1

4 2
2
5
-3
9

Output 1

3 7

Input 2

5 5
1
2
3
4
5

Output 2

1 1

Input 3

1 10
-1

Output 3

-1

Note

Example 1: If $n=2$, the machine would solve 3 problems. However, if $n > 7$, the machine can solve at most 1 problem. Consider what happens when $n=4$: - First second: The machine writes 2 lines. - Second second: The machine writes 5 more lines, totaling 7 lines; it submits and ACs the problem. - Third second: The machine deletes 3 lines, leaving 0 lines. - Fourth second: The machine writes 9 lines, totaling 9 lines; it submits and ACs the problem. It ACs a total of two problems.

Example 2: The machine ACs 5 problems in 5 seconds, so it must AC one problem every second. Thus, $n$ must be 1.

Example 3: The machine ACs 10 problems in 1 second. This is impossible. Output -1.