问题 D: 不醒人室

内存限制:256 MB 时间限制:5 S
题面:Markdown 评测方式:文本比较 上传者:
提交:4 通过:2

题目描述

你是一名前一天打完 CF,第二天还要去上课的大学生,但前一天打完 CF 后一天要早八实在是太痛苦了,因此你决定在课间小憩一下来使得自己能够不太困。 你今天一共 $n$ 节课,每节课 $b_i$ 时刻开始,$e_i$ 时刻结束。你会小憩 $m$ 次,$s_i$ 时刻开始睡,$t_i$ 时刻醒过来,睡醒之后你可以保持接下来 $2\times (t_i-s_i)$ 分钟不困,但是超过这个时间你就会很困。每次小憩都会刷新你不困的时间段,而不会叠加。例如在 $[1,2]$ 时小憩,会让你在 $[2,4]$ 时间段不困。如果你又在 $[3,5]$ 小憩,那么你下一个不困的时间段为 $[5,9]$。 但你的课任老师都十分严厉,他们不想看到有人上课表现出很困的状态或是就在睡觉,因此你的小憩时间不能跟上课时间重合。例如你上课的时间是 $[1,3]$ 与 $[4,5]$,那你的小憩不能为 $[2,4]$,因为你会在第一节课上睡觉。但如果小憩时间为 $[3,4]$ 的话是可以被接受的,因为此时视为在时刻 $3$ 老师下课后的瞬间,你正好开始小憩,时刻 $4$ 老师走进教室,你正好醒来,因此老师并不会看到你上课睡觉,并且你在第二节课上不会很困。请注意时刻 $0$ 时你处于[b]很困的状态[/b]。 因为你不想惹老师生气同时又想稍微休息下,因此你想知道你所拟定的计划是否能够满足要求。

输入格式

第一行一个整数 $T$($1\le T\le 10^4$),表示测试数据组数。 对于每组数据,第一行两个整数 $n$ 和 $m$($1\le n,m\le 10^5$),分别表示课的节数和你小憩的时间段。 接下来 $n$ 行,每行两个整数 $b_i,e_i$($0\le b_i\lt e_i\le 10^9$),分别表示课的开始和结束时间。保证 $0\le b_1\lt e_1\lt b_2\lt e_2\lt \ldots\lt b_n\lt e_n$。 接下来 $m$ 行,每行两个整数 $s_j,t_j$($0\le s_j\lt t_j\le 10^9$),分别表示小憩的开始和结束时间。保证 $0\le s_1\lt t_1\lt s_2\lt t_2\lt \ldots\lt s_m\lt t_m$。 保证对于所有数据,满足 $\sum n\le 5\times 10^5,\sum m\le 5\times 10^5$。

输出格式

如果存在一节课你会很困或就在睡觉,输出 $\texttt{No}$,否则输出 $\texttt{Yes}$。

输入样例 复制

2
3 2
30 45
60 90
120 180
0 30
90 120
3 2
30 45
60 90
120 180
0 20
90 120

输出样例 复制

Yes
No