Minimum Robot Flips for Lawn Mowing

You are given n robots and a lawn represented as the interval \([0,L]\). Each robot is located at position \(x\) and has a range \(r\). When activated, a robot can mow a contiguous segment of the lawn. By default, a robot mows in the rightward direction, covering the interval
\[ [x,\; x+r] \]
However, before starting, you are allowed to flip the direction of some robots. A flipped robot mows in the opposite direction, covering the interval
\[ [x-r,\; x] \]
Please note that each robot can only be used once in one of the two possible orientations. Your task is to determine the minimum number of robots you need to flip such that the union of the mowed segments covers the entire lawn \([0,L]\). If it is impossible to mow the whole lawn, output -1.

inputFormat

The first line contains two integers \(n\) and \(L\) (the number of robots and the length of the lawn, respectively). Each of the following \(n\) lines contains two integers \(x\) and \(r\), representing the position and range of a robot. All values are integers. Note that if an interval goes below 0 or above \(L\), it is effectively clamped to \(0\) or \(L\) respectively.

By default, every robot has the rightward orientation (mowing \([x, x+r]\)); if you flip it, it mows leftward (mowing \([x-r, x]\)).

outputFormat

Output a single integer, the minimum number of robots that must have their direction flipped so that the entire lawn \([0,L]\) is mowed. If it is impossible to cover \([0,L]\) no matter how you flip, output -1.

sample

3 10
0 5
5 5
2 3

0