1482 : 什么时候能退休啊

时间限制Time Limit
1 秒Sec
内存限制Memory Limit
128 兆MB
提交次数Submitted
0 次Times
通过次数Solved
0 次Times

题目描述Description

人生剧本你早就在天堂看过了,你之所以选择这个剧本是因为你觉得这一生有你认为值得的地方

DOGGOD 还没有找到人生的志向,现在只想着什么时候能退休。

假设 DOGGOD 能活 n 年,他每年的固定收入为 a_i 元,每年的固定支出为 b_i 元

当然!人生总是充满着各种机遇!聪明的你看过 DOGGOD 的人生剧本,发现他这一生会有 m 场机遇,每一场机遇都会带来一些收入或支出 c_j

DOGGOD 认为这辈子只要能养活自己就可以了,因此当他发现他的存款足够其生活下去(在仙逝之时存款不少于 0 元),他会选择彻底退休。这意味着他的固定收入不再是 a_i 元,而是 0 元

注意:当 DOGGOD 在第 x 年选择退休,那么他第 x 年到第 n 年的固定收入都为 0 元 (包括当年 x),但固定支出和机遇仍然不变

聪明的你能帮他算一下他最早能在第几年退休吗

输入格式Input

第 1 行包括两个正整数 n, m (1 \le n,m \le 200),代表着 DOGGOD 能活 n 年 以及 DOGGOD 将会有 m 个机遇

第 2 行包括 n 个正整数 a_i (1 \le a_i \leq 10^9),代表着 DOGGOD 第 i 年的固定收入

第 3 行包括 n 个正整数 b_i (1 \le b_i \leq 10^9),代表着 DOGGOD 第 i 年的固定支出

第 4 行 到 第 3 + m 行,每行包括两个整数 y_j (1 \le y_i \le n), c_j (-10^9 \le c_j \le 10^9),代表着 DOGGOD 会在第 y_j 年遇到一场机遇,带来一些收入或支出 c_j

输出格式Output

如果 DOGGOD 能成功退休,则输出一个整数 x,代表其在第 x 年退休

如果 DOGGOD 能无法退休,则输出 kaibai

样例Sample

提示Hint

DOGGOD 如果第一年就不工作(出生就不工作)

那么他的收入是 10( 机遇 3 )+ 30 ( 机遇 2 )

支出是 7 ( 第三年固定支出 ) + 20 ( 机遇 1 )

最终的存款为 13 元

得出结论:DOGGOD 不用工作!

出题Author

dgsvygd