[USACO17FEB] Why Did the Cow Cross the Road I S




Farmer John's cows are trying to learn to cross the road effectively. Remembering the old "why did the chicken cross the road?" joke, they figure the chickens must be experts on crossing the road, and go off in search of chickens to help them. 农夫约翰的牛们正在尝试去学会高效地穿越马路。熟知经典的笑话“为什么鸡要过马路?”,他们想到鸡一定是过马路的专家,便动身寻找能够帮助它们的鸡。 As it turns out, chickens are very busy creatures and have limited time to help the cows. There are $C$ chickens on the farm ($1 \leq C \leq 20,000$), conveniently numbered $1 \ldots C$, and each chicken $i$ is only willing to help a cow at precisely time $T_i$. The cows, never in a hurry, have more flexibility in their schedules. There are $N$ cows on the farm ($1 \leq N \leq 20,000$), conveniently numbered $1 \ldots N$, where cow $j$ is able to cross the road between time $A_j$ and time $B_j$. Figuring the "buddy system" is the best way to proceed, each cow $j$ would ideally like to find a chicken $i$ to help her cross the road; in order for their schedules to be compatible, $i$ and $j$ must satisfy $A_j \leq T_i \leq B_j$. 牛们发现,鸡是一种特别繁忙的动物,并且只有一定的时间来帮助它们。农场上共有$C$ 只鸡($1\le C\le 20000$),十分便利地被编号为$1...C$, 而且,每只鸡$i$ 只有恰好在时间$T_{i}$ 时才会愿意帮助牛们。而从不慌张的牛们,有更加灵活的时间安排。农场上共有$N$ 只牛($1\le N\le 20000$),也十分便利地被编号为$1...N$,牛$j$ 在时间$A_{j}$ 到$B_{j}$ 之间可以穿过马路。想到“小伙伴系统”是最好的行进方式,每只牛$j$ 会理想地愿意找到一只鸡$i$ 来帮助她穿过马路;为了是它们的时间表不冲突,$i$ 和$j$ 必须满足$A_{j}\le T_{i}\le B_{j}$ If each cow can be paired with at most one chicken and each chicken with at most one cow, please help compute the maximum number of cow-chicken pairs that can be constructed. 如果每头奶牛最多只能配一只鸡,而每只鸡最多只配上一头牛,请帮忙计算出可以构造的牛鸡对的最大数量。



The first line of input contains $C$ and $N$. The next $C$ lines contain $T_1 \ldots T_C$, and the next $N$ lines contain $A_j$ and $B_j$ ($A_j \leq B_j$) for $j = 1 \ldots N$. The $A$'s, $B$'s, and $T$'s are all non-negative integers (not necessarily distinct) of size at most 1,000,000,000 第一行的输入包括$C$ 和$N$。下面的$C$ 行包括$T1...TC$,再接下来的$N$ 行包括$A_{j}$ 和$B_{j}$($A_{j}\le B_{j}$),$j=1...N$。所有$A,B$ 与$T$ 都是非负整数(可能相等),并皆小于等于$1,000,000,000$。


Please compute the maximum possible number of cow-chicken pairs. 请计算最大的可行牛-鸡配对数。


输入样例 #1

5 4
2 5
4 9
0 3
8 13

输出样例 #1



感谢@Darkins 提供翻译