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