题目描述

农夫约翰的奶牛们发现，他田地里山脊上生长的三叶草格外优质。为了给三叶草浇水，农夫约翰正在山脊上安装洒水器。

为了便于安装，每个洒水器喷头都必须安装在山脊上（我们可以将山脊看作是一条长度为(L)（(1 ≤ L ≤ 1000000)；(L)是偶数）的一维数轴）。

每个洒水器向山脊两侧的地面洒水，洒水半径是一个在(A)到(B)（(1 ≤ A ≤ B ≤ 1000)）范围内的整数。农夫约翰需要以一种方式给整个山脊浇水，使得山脊上的每个位置都恰好被一个洒水器喷头覆盖，并且约翰不会向山脊两端之外的地方洒水。

农夫约翰的(N)（(1 ≤ N ≤ 1000)）头奶牛各自有一片特别喜欢的三叶草生长范围（这些范围可能会重叠）。这些范围由一个闭区间((S, E))定义。每头奶牛喜欢的范围都必须由一个洒水器来浇水，这个洒水器的洒水范围可能会超出给定的范围。

找到覆盖整个山脊且不重叠所需的最少洒水器数量。如果无法为农夫约翰设计出洒水器喷头的配置方案，则输出(-1)。

输入

第(1)行：两个用空格分隔的整数：(N)和(L)

第(2)行：两个用空格分隔的整数：(A)和(B)

第(3)行到(N + 2)行：每行包含两个整数(S)和(E)（(0 ≤ S < E ≤ L)），分别指定某头奶牛喜欢的范围的起始和结束位置。位置是从山脊起点开始的距离，因此范围在(0)到(L)之间。

输出

第(1)行：所需的最少洒水器数量。如果无法为农夫约翰设计出洒水器喷头的配置方案，则输出(-1)。

2 8
1 2
6 7
3 6

3

提示

输入细节： 在长度为(8)的山脊上有两头奶牛。洒水器喷头的整数洒水半径范围是(1)到(2)（即(1)或(2)）。一头奶牛喜欢(3)到(6)的范围，另一头奶牛喜欢(6)到(7)的范围。

输出细节： 需要三个洒水器：一个安装在位置(1)，洒水距离为(1)；一个安装在位置(4)，洒水距离为(2)；一个安装在位置(7)，洒水距离为(1)。第二个洒水器浇到了第二头奶牛喜欢的范围（(3)到(6)）内的所有三叶草。最后一个洒水器浇到了第一头奶牛喜欢的范围（(6)到(7)）内的所有三叶草。这里有一个示意图：

                 |-----c2----|-c1|       cows' preferred ranges
     |---1---|-------2-------|---3---|   sprinklers
     +---+---+---+---+---+---+---+---+
     0   1   2   3   4   5   6   7   8

洒水器在位置(2)和(6)处不被认为是重叠的。

来源

USACO 2004 年 12 月 金牌赛