There are few students who are working in a project. Some of them are from college C1 and others are from college C2. The mentor asked everyone to first read a book. There is only one copy of the book which is available and is kept in a room. For each student we know the time at which he/she enters the room and the amount of time he/she spends reading the book. Once any student starts reading the book, he/she reads it in a one go i.e. without being interrupted until he/she finishes.
But the only constraint is that the book can be read by only one student from college C1 at a particular time i.e no other student is reading the same book parallely. While more than one students from college C2 can share the book while reading.
Find the minimum time when all the students can finish reading the book.
Input
- The first line contains two space separated integers N and M denoting the number of students from college C1 and C2 respectively.
- Next N lines contains the entering and reading time for students from college C1.
- Next M lines contains the entering and reading time for students from college C2.
Output
- Output the answer in a single line. (minimum time when all the students can finish reading the book)
Constraints
- 1 <= N, M <= 3000
- 1 <= entering time <= 107
- 1 <= reading time <= 105
Sample Input 1
1 2
1 3
2 4
3 3
Sample Output 1
8
Explanation
The student from C1 starts reading as soon as he enters, he finishes at time = 4. The other two students from C2 have already entered. They read in parallel. Student S1 from C2 finishes at time = 8 and S2 from C2 finishes at time = 7.
Scoring
Scores will be calculated as follows:
Score = (1 - c / 8000) * 250, where c is the number of characters in your code. In case the characters exceed 8000, your score will be zero.
S1, S3 and S4 from C2 each start reading as soon as they enter (they read in parallel). Then S1, S2 and S3 from C1 each read in any order. Then finally S2 from C2 reads the book.
