Problem D: University Hotel[Medium]

Problem D: University Hotel[Medium]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2309  Solved: 223
[Submit][Status][Web Board]


As you know, every university has a hotel but it is always hard to book a room. Every year, thousands of orders fly to the hotels. The boss of a hotel in S University is busy, and hopes to make a program to deal with the orders. As he knows you are good at programming, he turns to you for help. The problem is described as follows:

We need to deal with the orders in the following n days. During the n days, there will be ri rooms available. And there are orders, every order is described by 3 integers, which are dj, sj, trespectively. This indicates the customer need to book dj rooms from day sj to t (inclusive). To simplify, we need not to care whether the customer get the same room everyday.

The principle for booking rooms is First come, First get, i.e., we need to assign rooms for the customers by the chronological sequence of the orders. If any one order can’t be satisfied, we need to stop assignment and inform the customer to modify the order. Here, the dissatisfaction refers to that at least one day during day sto t the number of remaining rooms is less than dj.

Now we need to know, whether there are orders can't be satisfied. And if so, we should inform which customer to modify the order.


The input contains several test cases. For each test case:

The first line will be 2 integers n, m, which are the number of days and orders.

The second line contains n integers the ith number is ri, indicates the number of rooms can be booked that day.

Then there are m lines, every line has 3 integers dj, sj, tj, indicates the number of rooms  to be booked, the begin day and end day of the jth order.



If all orders can be satisfied, the only output is one line, contains an integer 0, otherwise output two line, the first line output -1, and the second line output the index of the order that should be modified.

Sample Input

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

Sample Output