D.Rad Radish Dishes（酷炫萝卜菜肴）

输入： 标准输入（stdin） 输出： 标准输出（stdout） 内存限制： 256 MB 时间限制： 2.0 秒

• problem statement
• submit
• submissions

---

题目描述

Arlene 是一位世界闻名的萝卜种植者。现在正值萝卜种植季，她非常忙碌。

萝卜是一种生长很快的作物。一株萝卜在种下：

$$M$$

天后就可以收获。

在萝卜种植季的前 (M) 天里，Arlene 每天都种下了一定数量的萝卜。

---

在接下来的：

$$N$$

天里，Arlene 每天都会进行以下工作：

• 收获萝卜；
• 种植萝卜；
• 出售萝卜。

在第 (i) 天的早上，Arlene 会：

1. 收获所有已经成熟、可以收获的萝卜；
2. 再种下 (p_i) 个新的萝卜。

到了下午，她会前往农贸市场，并希望恰好卖出：

$$s_i$$

个萝卜。

但是，即使 Arlene 进行了非常细致的规划，有时候她当天收获的萝卜数量仍然不足以恰好卖出 (s_i) 个。

在这种情况下：

她当天不会卖出任何萝卜。

同时，为了了解自己的计划到底差了多少，她想知道：

如果只考虑当前已经种下的萝卜，她还需要再等待多少天，才能拥有至少 (s_i) 个萝卜可以出售？

Arlene 请你帮忙编写一个程序来完成这些计算。

---

输入格式

第一行包含两个用空格分隔的整数：

N M

第二行包含 (M) 个用空格分隔的整数，表示 Arlene 在种植季最开始的 (M) 天里，每天种下的萝卜数量。

接下来的 (N) 行，每行包含两个用空格分隔的整数：

p_i s_i

其中：

• (p_i) 表示这一天新种下的萝卜数量；
• (s_i) 表示 Arlene 这一天希望卖出的萝卜数量。

---

输出格式

输出 (N) 行。

每行输出一个整数，表示：

Arlene 至少还需要等待多少天，才能拥有足够的萝卜用于出售。

如果即使等待当前所有已经种下的萝卜成熟，也仍然不够，则输出：

-1

---

数据范围

$$1\le N\le100000$$ $$2\le M\le100000$$

任意一天种植或出售的萝卜数量最多为：

$$1000000000$$

---

子任务

• 子任务 1（+22%）：

$$N,M\le1000$$

• 子任务 2（+27%）：

每天的情况都会满足下面两种之一：

• 当前已经种下的萝卜总量不足；

• 或者当天已经拥有足够的萝卜，可以卖出 (s_i) 个。

• 子任务 3（+17%）：

对于所有：

$$1\le i\le N$$

都有：

$$p_i,s_i\le100$$

• 子任务 4（+34%）：

没有额外限制。

---

注意事项

如果你使用的是对整数类型比较敏感的语言，例如：

• C++
• Java
• C

那么请务必使用 64 位整数类型，避免发生整数溢出。

64 位整数类型包括：

• C / C++：long long
• C# / Java：long

---

样例说明

样例 1

在这个样例中：

$$N=3$$

并且：

$$M=4$$

在种植季最开始的 4 天里，Arlene 分别种下：

4 3 5 1

个萝卜。

---

第 5 天

第一天种下的 4 个萝卜成熟并被收获。

同时，Arlene 又种下了：

1

个新的萝卜。

此时她拥有 4 个已经收获的萝卜。

她希望卖出：

2

个。

于是卖掉 2 个后，还剩：

2

个萝卜。

因为当天已经有足够的萝卜，所以不需要额外等待：

0

天。

---

第 6 天

第二天种下的：

3

个萝卜成熟并被收获。

同时，Arlene 又种下：

2

个新萝卜。

她原本还剩：

2

个已经收获的萝卜。

现在又收获 3 个，所以一共有：

$$2+3=5$$

个萝卜。

但是她希望卖出：

$$7$$

个，因此当前数量不足。

所以她当天不会出售任何萝卜。

如果她再等待 1 天，那么第三天种下的 5 个萝卜也会成熟。

此时她将拥有：

$$2+3+5=10$$

个萝卜。

这已经足够卖出 7 个。

因此需要等待：

1

天。

---

第 7 天

第三天种下的：

5

个萝卜成熟并被收获。

同时，Arlene 又种下：

8

个萝卜。

由于第 6 天没有出售任何萝卜，所以之前的 5 个萝卜仍然保留着。

现在又收获 5 个，因此一共有：

$$5+5=10$$

个萝卜。

Arlene 希望卖出：

5

个。

于是卖掉 5 个后，还剩：

5

个。

因此不需要额外等待：

0

天。

---

样例输入 1

3 4
4 3 5 1
1 2
2 7
8 5

样例输出 1

0
1
0

---

样例输入 2

4 2
4 2
1 8
4 6
1 9
3 2

样例输出 2

-1
0
-1
0

测试点编号	层级	N	M	数据特征	覆盖点与设计目的
1	弱数据	1		最小规模，当前库存充足	覆盖直接销售并输出 0
2				当前为零，今天种植量恰好满足	覆盖等待一天、下界恰好命中
3				当前和未来总量均不足	覆盖输出 -1
4	正常数据	4	2	充足、短缺、再次销售、无解交替	检查库存结转及短缺时不扣库存
5		6	3	种植量和需求量全部为零	覆盖零值、重复前缀和及 s=0
6		7	4	零值与非零值交错，多次恰好满足	检查 lower_bound 在重复前缀和中的行为
7		8	3	库存连续积累，销售与等待交替	覆盖剩余库存参与后续判断
8	较强数据	10	5	等待时间覆盖 1～M，包含无解	检查搜索区间两端及当天种植的萝卜
9	极限数值	6	3	数量达到 10¹⁸ 级别	检查 long long 运算和大数边界
10	极限规模	1000		确定性混合数据，含零值、突增和重复模式	覆盖较大输入、长等待及二分查找稳定性