天帝被愚公的诚心感动，命令手下的仙人帮助移山。 然而仙人的法术也是有局限性的，山势连绵起伏，法术并不能直接把山移走。每次施法，可以把一段连续区域的山头移走相同高度。现在愚公想知道什么时候会有至少一个山头高度小于等于0 给出一个长度为 的数组 ，和 表示山头的高度和可以施法的次数，每次施法还会给出左右端点 和高度 ，表示将 依次减去 。问在哪次操作之后存在一个 ？（数据保证这样的时刻存在。）

输入描述:

第一行两个数  和 ，表示山头数量和施法次数。第二行个数，分别表示 ，即第一个山头到第 个山头的高度。接下来m行，每行三个数，表示一次施法的具体参数。，均为整数

输出描述:

输出一个整数，表示答案。数据保证答案存在。