题目描述
约翰在山脊上安装了洒水装置。每个洒水器都必须沿着山脊安装，山脊的长度为L （1≤L ≤1000000，L 是偶数）。每个洒水器都沿山脊在两个方向上浇灌地面一段距离。每个洒水器的喷洒半径均为[a , b ]（1≤a ≤b ≤1000）内的整数。约翰需要用一些洒水器来浇灌整个山脊，且浇灌范围不会超过山脊的末端。
约翰的n （1≤n ≤1000）头牛都有一个特别喜欢的范围[s , e ]（这些范围可能重叠）。对每头牛喜欢的范围都必须用一个洒水器，洒水器可能会（或不会）喷到指定的范围之外。找到浇灌整个山脊而不重叠所需的洒水器最小数量。
约翰的n （1≤n ≤1000）头牛都有一个特别喜欢的范围[s , e ]（这些范围可能重叠）。对每头牛喜欢的范围都必须用一个洒水器，洒水器可能会（或不会）喷到指定的范围之外。找到浇灌整个山脊而不重叠所需的洒水器最小数量。
输入
第1行包含两个整数n 和L 。第2行包含两个整数a 和b 。第3..n +2行中的每一行都包含两个整数s 和e （0≤s <e ≤L ），分别表示一头牛喜欢的范围的开始位置和结束位置。位置以到山脊起点的距离表示，所以在0..L 范围内。
输出
单行输出洒水器最小数量。若无法设计洒水装置，则输出-1。
样例输入 Copy
2 8
1 2
6 7
3 6
样例输出 Copy
3
提示
根据输入样例，一共有两头牛，山脊的长度为8。洒水器的喷洒半径为[1,2]（即1或2）。一头牛喜欢3-6区域，另一头牛喜欢6-7区域。
我们需要3个洒水器：一个在1处，喷洒半径为1；一个在4处，喷洒半径为2；一个在7处，喷洒半径为1。第2个洒水器浇灌了第2头牛喜欢的三叶草。最后一个洒水器浇灌了第1头牛喜欢的三叶草，如下图所示。喷水器在2和6处不被视为重叠。
我们需要3个洒水器：一个在1处，喷洒半径为1；一个在4处，喷洒半径为2；一个在7处，喷洒半径为1。第2个洒水器浇灌了第2头牛喜欢的三叶草。最后一个洒水器浇灌了第1头牛喜欢的三叶草，如下图所示。喷水器在2和6处不被视为重叠。