Program Description
In RI, RI-WLAN requires students to login before one can access the Internet. Ranald finds it a hassle and thus wanted to create a new Wifi network, for the whole school!
However, he encountered a problem. He has setup the routers around the school, but he now realises that different routers have different range of services, such that he does not need to utilize all the routers in order to provide Wifi-coverage to the whole school!
For simplicity sake, he has asked you to solve the problem of Wifi-coverage along the corridor. The width of the corridor can be neglected, translating this to a 1D problem. *hint hint*
You are supposed to calculate the minimum amount of routers Ranald has to turn on in order to allow anyone along the corridor to enjoy Wifi access.
Input
The first line on input consists of 2 integers, l followed by n. n is the number of routers Ranald has installed. l is the length of the corridor Ranald intends to provide Wifi access to, in metres.
The following n lines consists of 2 integers each, ai, the distance of the router from the start of the corridor in metres, and ri, the radius of the range the router can provide Wifi access to.
For 50% of the testcases, n will not be more than 1000 and l will not be more than 50000.
For 100% of the testcases, n will not be more than 50000 and l will not be more than 1000000000.
Output
Output a single integer on a single line, denoting the minimum number of routers Ranald needs to turn on in order to provide Wifi access to the entire corridor (without interruption).
In the event that coverage along the entire corridor is not possible, output -1 instead.
Sample Input 1
20 5
3 4
7 2
10 3
15 7
20 9
Sample Output 1
3
Explanation of Output 1
Router 1 (Pos 3 and Range 4) can cover the corridor from 0m to 7m. Router 3 (Pos 10 and Range 3) can cover the corridor from 7m to 13m. Router 4 (Pos 15 and Range 7) can cover the corridor from 8m to 22m. With this 3 routers, there's Wifi coverage from 0m to 20m, and that is the minimum number of routers required.
Sample Input 2
20000 5
3 4
7 2
10 3
15 7
20 9
Sample Output 2
-1
Explanation of Output 2
The input is the same as Sample Input 1 but the length of the corridor is 20000. Therefore, the routers do not have enough range to provide Wifi coverage for the entire corridor.