Comet OJ

C0968 [SHOI2015]自动刷题机

内存限制：256 MB 时间限制：1000 ms

题目描述

曾经发明了信号增幅仪的发明家 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$。

样例

样例输入 1

4 2
2
5
-3
9

样例输出 1

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$。