2437: LazyLie的草坪

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:35 解决:6

题目描述

LazyLie有个长L米、宽W米的草坪,草坪里装有n个浇灌喷头。每个喷头都装在草坪的中心线上(即距离草坪上下两端各W/2米),喷头浇灌的范围是是一个圆。我们知道每个喷头的位置(距离草坪最左端的距离),以及每个喷头所能浇灌的半径。

LazyLie想知道,如果要同时浇灌整块草坪,最少需要打开多少个

输入

第一行,三个整数nLW

之后n行,每行两个整数XR,表示位置和半径。

输出

输出一行一个数字,表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开也不能浇灌整块草坪,则输出-1

样例输入 复制

9 20 2
2 1
1 2
6 2
5 3
9 2
12 3
16 2
17 1
19 4

样例输出 复制

6

提示

【输入样例2

3 10 1

5 3

1 1

9 1

【输出样例2

-1

 

对于20%的数据 n<=25

对于50%的数据 n<=5000

对于100%的数据 n<=1000000,w<=l<=2^31-1