#P18582. Mortgage

Mortgage

Mortgage

Andrej 希望将来买一套房子,正在规划自己的收入和贷款。对于未来的 n 个月,第 i 个月在扣除其他开支之后,可用于偿还房贷的收入为 a_i。这个数可能为负。

一份房贷从第 s 个月开始,持续 k 个月,即从第 s 个月到第 s+k−1 个月,每个月都需要偿还相同的整数金额 x。

在这段时间内,某个月偿还之后剩余的钱可以存起来,用于之后月份的还款。但是,他不能使用第 s 个月之前的任何收入或储蓄;那些钱都会花在当前的房租和生活上。贷款期间,他必须在每个月都能完成当月还款。

给定未来 n 个月的收入,以及 m 个不同的贷款时间区间。请对每个区间求出他能够负担的最大整数月供。如果该最大值严格小于 0,按输出格式报告。

输入格式

第一行包含两个整数 n 和 m,分别表示月份数和询问数。

第二行包含 n 个整数 a_1, a_2, …, a_n。

接下来 m 行,每行包含两个整数 s_i 和 k_i,表示第 i 份房贷从第 s_i 个月开始,持续 k_i 个月。

每个询问独立考虑,贷款开始前可用于该贷款的储蓄均为 0。

输出格式

输出 m 行。对于每个询问:

  • 若能够负担的最大整数月供大于或等于 0,输出该整数。
  • 若它严格小于 0,输出 stay with parents。

上述英文短语不含引号,全部小写,单词之间各一个空格。答案为 0 时,应当输出 0。

数据范围

  • 1 ≤ n, m ≤ 2×10^5。
  • −10^9 ≤ a_i ≤ 10^9。
  • 1 ≤ s_i ≤ n。
  • 1 ≤ k_i,且 s_i+k_i−1 ≤ n。

输入是一组数据。询问给出的是“起点、长度”,不是“左右端点”。

样例输入 1

9 5
6 1 10 9 5 -2 3 1 -1
3 6
1 4
3 3
6 1
8 2

样例输出 1

4
3
8
stay with parents
0

样例说明

第一个询问中,最大月供为 4。若每个月偿还 5,他会在最后一次还款时资金不足。

第四个询问只包含第 6 个月,该月收入为负,因此输出 stay with parents。