题目描述

众所周知，chatgpt已经成为大家的好帮手。它可以帮助我们编写程序，解决问题。

它总能找到题目的正确做法，然后开始写程序。每秒，chatgpt的代码生成模块会有两种可能的结果： 1. 写了 $x$ 行代码； 2. 心情不好，删掉了之前写的 $y$ 行代码。如果 $y$ 大于当前代码长度，则相当于全部删除。

对于一个 OJ，存在某个固定的长度 $n>0$，一旦chatgpt在某秒结束时积累了大于等于 $n$ 行的代码，它就会自动提交并 AC 此题，然后开始写下一题 （ 弃置之前的所有代码）。西西在某个 OJ 上跑了一天的chatgpt，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的 $n$ 究竟是多少。所幸他知道自己在 OJ 上 一共切了 $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

数据范围与提示

对于 $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$