3480: 1424:【例题3】喷水装置

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

题目描述

给定一个长为 L 米,宽为 W 米的矩形草坪,草坪中心线上装有 n 个浇灌喷头。每个喷头的位置是离草坪中心线左端的距离,并且知道它能覆盖到的浇灌范围(即喷洒半径)。你的任务是计算出最少需要打开多少个喷头以同时浇灌整块草坪。如果即使所有喷头都打开也不能完全覆盖整个草坪,则输出 -1

输入

  • 第一行是一个整数 T 表示测试数据组数。
  • 每组数据的第一行包含三个整数 nL 和 W,分别表示喷头的数量、草坪的长度以及宽度。
  • 接下来的 n 行,每行包含两个整数,分别表示一个喷头的位置(离草坪中心线左端的距离)及其浇灌半径。

输出

对每组测试数据输出一个数字,表示要浇灌整块草坪所需喷头数目的最小值。如果无法通过打开任意数量的喷头来覆盖整个草坪,则输出 -1。

样例输入 复制

3
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1

样例输出 复制

6
2
-1

提示

  • 数据范围:对于 100% 的数据,n15000