题目描述

曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明：自动刷题机——一种可以自动 AC 题目的神秘装置。

自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，自动刷题机的代码生成模块会有两种可能的结果：

1. 写了 $x$ 行代码；
2. 心情不好，删掉了之前写的 $y$ 行代码。如果 $y$ 大于当前代码长度，则相当于全部删除。

对于一个 OJ，存在某个固定的长度 $n>0$，一旦自动刷题机在某秒结束时积累了大于等于 $n$ 行的代码，它就会自动提交并 AC 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的 $n$ 究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了 $k$ 道题，希望你计算 $n$ 可能的最小值和最大值。

输入格式

第一行两个整数 $l, k$，表示刷题机的日志一共有 $l$ 行，一共了切了 $k$ 题。
第二行 $l$ 个整数 $x_1, \dots, x_l$。$x_i \geq 0$ 表示写了 $x_i$ 行代码，$x_i < 0$ 表示删除了这道题的 $-x_i$ 行代码。

输出格式

输出两个数 $a, b$，分别代表 $n$ 可能的最小值和最大值。如果不存在这样的 $n$ 则输出 $-1$。

样例

input

4 2
2
5
-3
9

output

3 7

如果 $n = 2$ 那么刷题机就会切掉 $3$ 题。但如果 $n > 7$ 刷题机最多只能切 $1$ 题。考虑 $n = 4$ 时发生了什么。

• 第一秒：刷题机写了 $2$ 行。
• 第二秒：刷题机又写了 $5$ 行，共有 $7$ 行，提交，自信 AC。
• 第三秒：刷题机删掉了 $3$ 行，共有 $0$ 行。
• 第四秒：刷题机写了 $9$ 行，共有 $9$ 行，提交，自信 AC。一共 AC 了两题。

数据范围与提示

对于 $20\%$ 的数据，$l \leq 10$；
对于 $40\%$ 的数据，$l \leq 100$；
对于 $60\%$ 的数据，$l \leq 2000$；
对于 $100\%$ 的数据，$l \leq 100000,k\le 10000$，$-10^9 \leq x_i \leq 10^9$。