Alice and Bob like to play a lot. Unfortunately, their schedule is a little busy nowadays and they are finding it hard to find mutually common free time.
Given two list of intervals of free times; one of Alice and the other corresponding to Bob, you have to find out the total mutually common free time of Alice and Bob. For each separate list of intervals, it’s ensured that the no two intervals in the list intersect each other, however, they may touch each other.
For example, if Alice’s list of intervals is { [1, 4], [6, 10], [13, 16] }, that means that she is free for three hours, from t = 1 to t = 4. Similarly, she is free for 4 hours from t = 6 to t = 10. If Bob’s list of intervals is { [2, 5], [10, 15] }, then from t = 2 to t = 4, both of them are free, which leads to 2 hours of free time, as well as from t = 13 to t = 15, which is another two hours of mutually common free time. Therefore the total amount of free time is 4.
Input
- The first line of each test case contains two space-separated integers n,mn,m where nn denotes the size of interval list of Alice and mm denotes that of Bob.
- Each of next nn lines contains two space-separated integers si,eisi,ei denoting that the ii-th interval starts from sisi and ends at eiei.
- Similarly, the next mm lines contain the interval list of Bob.
Constraints
- 1≤n,m≤1051≤n,m≤105
- 1≤si≤ei≤1091≤si≤ei≤109
Subtasks
- For 30% of the score: 1≤n≤1000,1≤si≤ei≤1061≤n≤1000,1≤si≤ei≤106
- Remaining 70%: No extra constraints.
Sample Input
3 2
1 4
6 10
13 16
2 5
10 15
Sample Output
4
CREATE AN ACCOUNT TO GET NOTIFICATIONS ABOUT
NEW QUESTIONS AND ANSWERS.
DOWNLOAD ATTACHMENT FOR ANSWER: