Minimum Street Lamps Coverage

You are given a road represented by the interval ([0, N]) and a set of street lamps. Each street lamp is located at position (P) and illuminates a segment of the road with radius (R), covering the interval ([\max(0, P-R), \min(N, P+R)]). Your task is to determine the minimum number of street lamps required such that the entire road is illuminated. If it is impossible to cover the entire road with the available street lamps, output (-1).

For each test case, the input starts with two integers (M) and (N) where (M) is the number of street lamps and (N) is the endpoint of the road. Then follow (M) lines, each with two integers (P) and (R) indicating the position and the range of a lamp respectively.

The problem can be solved using a greedy algorithm by first computing the illuminated intervals, sorting them, and then selecting the minimum number of intervals (lamps) to cover the entire road.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) representing the number of test cases. For each test case:

• The first line contains two integers: (M) (the number of street lamps) and (N) (the endpoint of the road).
• Each of the next (M) lines contains two integers: (P) (the position of the lamp) and (R) (the illumination range of the lamp).

outputFormat

For each test case, output a single integer representing the minimum number of street lamps required to cover the road from 0 to (N). If the road cannot be fully covered, output (-1). Each answer should be printed on a new line to standard output (stdout).## sample

2
3 10
1 5
5 3
8 2
4 20
2 8
5 7
13 3
18 5

2
3