3263. 丽娃河的狼人传说

单点时限: 2.0 sec

内存限制: 256 MB

丽娃河是华师大著名的风景线。但由于学校财政紧缺,丽娃河边的路灯年久失修,一到晚上就会出现走在河边要打着手电的情况,不仅非常不方便,而且影响安全:已经发生了大大小小的事故多起。

方便起见,丽娃河可以看成是从 的一条数轴。为了美观,路灯只能安装在整数点上,每个整数点只能安装一盏路灯。经专业勘测,有 个区间特别容易发生事故,所以至少要安装一定数量的路灯,

请问至少还要安装多少路灯。

输入格式

第一行一个整数 ,表示测试数据组数。

对于每组数据:

  • 第一行三个整数

  • 第二行 个不同的整数用空格隔开,表示这些位置一开始就有路灯。

  • 接下来 行表示约束条件。第 行三个整数 表示:第 个区间 至少要安装 盏路灯

输出格式

对于每组数据,输出 Case x: y。其中 x 表示测试数据编号(从 1 开始),y 表示至少要安装的路灯数目。如果无解,y 为

样例

Input
3
5 1 3
1 3 5
2 3 2
5 2 3
1 3 5
2 3 2
3 5 3
5 2 3
1 3 5
2 3 2
4 5 1
Output
Case 1: 1
Case 2: 2
Case 3: 1

提示

因为今天不是满月,所以狼人没有出现。

418 人解决,681 人已尝试。

514 份提交通过,共有 2933 份提交。

3.1 EMB 奖励。

创建: 2 年,3 月前.

修改: 1 年,11 月前.

最后提交: 1 天,21 小时前.

来源: 2017 华东师范大学网赛

题目标签