PICAD  Crime at Piccadily Circus
Sherlock Holmes is carrying out an investigation into the crime at Piccadily Circus. Holmes is trying to determine the maximal and minimal number of people staying simultaneously at the crime scene at a moment when the crime could have been commited. Scotland Yard has already carried out a thorough investigation already, interrogated everyone seen at the crime scene and determined what time they appeared at the crime scene and what time they left. Doctor Watson offered his help to process the data gathered by Scotland Yard and find the numbers interesting Sherlock Holmes, but he has some difficulties. Help him!
Task
Write a program which
 reads from standard input the time interval during which the crime was commited and the data gathered by Scotland Yard,
 finds the minimal and the maximal number of people present simultaneously in the time interval when the crime could have been commited, (these numbers can be zero, though it would seem strange that noone was present at the crime scene when the crime was commited, but that's the type of crime Holmes and Watson have to deal with)
 writes the outcome to standard output.
Input
Ten test cases (given one under another, you have to process all!). The first line of each test case consists of two integer numbers p and k, 0<=p<=k<=100000000. These denote the first and the last moment when the crime could have been commited. The second line of each test case contains one integer n, 3<=n<=5000. This is the number of people interrogated by Scotland Yard. The next n lines consist of two integers  line i+2 contains numbers a_{i} and b_{i} separated by a single space, 0<=a_{i}<=b_{i}<=1000000000. These are the moments at which the ith person apperared at and left the crime scene respectively. It means that the ith person was at the crime scene for the whole time from moment a_{i} until moment b_{i} (inclusive).
Output
For every test case your program should write to the standard output only one line with two integers separated by a single space: the minimal and maximal number of people staying simultaneously at the crime scene, in the interval between moment p and k, (inclusive).
Example
Only one test case.
Input: 5 10 4 1 8 5 8 7 10 8 9 Output: 1 4
hide comments
sar_neil:
20171030 19:37:33
Will there always be 10 test cases? 

nadstratosfer:
20170917 03:57:45
What a nightmare to get right. As of now, 3600 submissions out of 5600 total are WAs. I was struggling even after looking at somebody else's correct code :(


minhthai:
20160417 17:31:33
so apparently, you have to do it 10 times in a row. So..many..WAs :(( 

Abhilash:
20150616 22:05:40
comments helped 

Govind Lahoti:
20150305 14:36:06
Nice problem 

AndrĂ© Balan [UFABC]:
20140320 04:41:53
Last edit: 20140320 17:42:07 

Ankit Chaudhary:
20140202 06:25:58
tricky tc :


Shubham Depp Bansal:
20130113 10:45:13
i am not getting the meaning of input 0.how can a man gets in at 0 time and leavs at the end of 0..i mean how?? 

The Bartender:
20101227 14:30:59
Be careful:


:D:
20100401 19:41:36
In a case when one interval stars right after another, you should assume that there is some time inbetween.

Added by:  Adam Dzedzej 
Date:  20040610 
Time limit:  13s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Internet Contest Pogromcy Algorytmow (Algorithm Tamers) Round IV, 2003 