题目描述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

来源Source