本题转译自 [NOIP2012 提高组] 借教室。 学校每天有一定数量的教室可供租借。现在你获得了接下去 天的空闲教室信息,第 天有 个教室可供租借。 系统一共有 份租借订单,已经按照申请时间从早到晚排序。第 份订单由一个三元组 描述,表示需要在第 天到第 天期间每天租借 个教室(包括第 天和第 天)。租借者对具体教室没有要求。 按照先到先得的原则处理订单。如果某个订单在其租借期间有任何一天剩余教室数量不足,则需要通知该申请人修改订单,并停止处理后续订单。 请判断是否存在无法满足的订单。如果存在,输出需要修改订单的申请人编号。
输入描述:
第一行输入两个整数  代表天数和订单的数量。第二行输入  个整数  代表每一天可用于租借的教室数量。此后  行,第  行输入三个整数  代表租借的教室数量、租借开始时间、租借结束时间。每行相邻的两个数之间均用一个空格隔开。天数与订单均用从  开始的整数编号。


输出描述:
如果订单无法完全满足,在一行上输出一个整数代表需要修改的订单申请人编号;否则,直接输出 。申请人编号即输入顺序,从 开始计数。
示例1

输入

4 3
2 5 4 3
2 1 3
3 2 4
4 2 4

输出

2

说明

\hspace{15pt}第一份订单满足后,这四天剩余的教室数为 \{0, 3, 2, 3\}
\hspace{15pt}第二份订单要求第二天到第四天每天提供 3 个教室,而第三天剩余的教室数为 2 ,因此无法满足。分配停止,通知第二个申请人修改订单。
示例2

输入

4 1
2 5 4 3
2 1 3

输出

0
加载中...