#2036. 「SHOI2015」自动刷题机

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cyand1317

题目描述

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

样例

样例输入

4 2
2
5
-3
9

样例输出

3 7

样例解释

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

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

数据范围与提示

对于 20\% 的数据, n \leq 10
对于 40\% 的数据, n \leq 100
对于 60\% 的数据, n \leq 2000
对于 100\% 的数据, n \leq 100000 -10^9 \leq x_i \leq 10^9