Assignments at IITK
All submissions for this problem are available.
The Department of CSE, IITK tried a new experiment by giving M algorithmic assignments to students in groups of size N. Students are allowed to divide an assignment into parts such that each part is solved by a different student. It must be noted that a student may do atmost one assignment at a time. Also, an assignment can be attempted by exactly one student at a time, it may not be the case that two different students be solving different parts of the same assignment at the same time.
Here at IITK every student is believed to have the same potential. The professors estimated the total number of student hours each assignment will require. Now as the student calendar is filled with a lot of interesting activities, this makes it difficult for the students to be always available for an assignment. Most of the times, they are involved in doing many interesting activities e.g., many of them must be participating in IOPC 2013 right now :)
The Department knows that the students of CSE, IITK are very competent and have knowledge of when an assignment will be put up, how much student hours it requires and the deadline of the assignments. The Professors must know that the students here are very moody. So, it is possible that a student gets bored of solving an assignment for a long time, leaves it in the middle to pick another assignment without wasting any time. The student may later come back to the earlier assignment or may ask one of his friends (of the group of N students) to solve it.
Your task is to help the Professors figure out if this experiment of theirs would be a success. In other words, figure out if it is possible for the group of N students to finish the given M assignments by the deadline.
The first line of the input contains an integer T denoting the number of test cases
First line of each test case contains two integers N the number of students and M the number of assignments given to the group.
The next N lines contain two integers S and E denoting the start and end time at which the student is free to solve his/her assignments.
The next M lines contain three integers A, D and H denoting the start time of the assignment, the deadline of the assignment and the expected student hours needed to complete the assignment respectively.
For each test case, output a single line containing “YES” (without quotes) if it is possible to complete all assignments by their deadline and “NO” (without quotes) otherwise.
- 1 ≤ T ≤ 120
- 1 ≤ N,M ≤ 50
- 0 ≤ S,E,A,D,H ≤ 107
Input: 1 2 2 1 5 3 4 1 5 3 2 4 2 Output: YES
|Time Limit:||0.121212 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions