#3145. [SHOI2015] 自动刷题机

[SHOI2015] 自动刷题机

题目背景

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

题目描述

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

1.写了 xx 行代码 2.心情不好,删掉了之前写的 yy 行代码。(如果 yy 大于当前代码长度则相当于全部删除。)

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

输入格式

第一行两个整数 l,kl , k,表示刷题机的日志一共有 ll 行,一共了切了 kk 题。

接下来 ll 行,每行一个整数 xix_i,依次表示每条日志。若 xi0x_i \geq 0,则表示写了 xix_i 行代码,若 xi<0x_i \lt 0,则表示删除了 xi-x_i 行代码。

输出格式

输出一行两个整数,分别表示 nn 可能的最小值和最大值。 如果这样的 nn 不存在,请输出一行一个整数 1-1

4 2
2
5
-3
9
3 7

提示

数据规模与约定

  • 对于 20%20\% 的数据,保证 l10l \le 10
  • 对于 40%40\% 的数据,保证 l100l \le 100
  • 对于 60%60\% 的数据,保证l2×103l \le 2 \times 10^3
  • 对于 100%100\% 的数据,保证 1l1051 \leq l \le 10^5109xi109-10^9 \le x_i \le 10^9