#P4995. [Usaco2017 Feb]Why Did the Cow Cross the Road

    ID: 4094 传统题 1000ms 256MiB 尝试: 157 已通过: 75 难度: 4 上传者: 标签>CF1500普及排序贪心按截止时间排序有序多重集合交换论证Silver

[Usaco2017 Feb]Why Did the Cow Cross the Road

题目描述

农夫约翰的牛们正在尝试去学会高效地穿越马路。熟知经典的笑话“为什么鸡要过马路?”,他们想到鸡一定是过马路的专家,便动身寻找能够帮助它们的鸡。

牛们发现,鸡是一种特别繁忙的动物,并且只有一定的时间来帮助它们。农场上共有CC 只鸡(1≤C≤200001\le C\le 20000),十分便利地被编号为1...C1...C, 而且,每只鸡ii 只有恰好在时间TiT_{i} 时才会愿意帮助牛们。而从不慌张的牛们,有更加灵活的时间安排。农场上共有NN 只牛(1≤N≤200001\le N\le 20000),也十分便利地被编号为1...N1...N,牛jj 在时间AjA_{j} 到BjB_{j} 之间可以穿过马路。想到“小伙伴系统”是最好的行进方式,每只牛jj 会理想地愿意找到一只鸡ii 来帮助她穿过马路;为了是它们的时间表不冲突,ii 和jj 必须满足Aj≤Ti≤BjA_{j}\le T_{i}\le B_{j}

如果每头奶牛最多只能配一只鸡,而每只鸡最多只配上一头牛,请帮忙计算出可以构造的牛鸡对的最大数量。

输入格式

第一行的输入包括CC 和NN。下面的CC 行包括T1...TCT1...TC,再接下来的NN 行包括AjA_{j} 和BjB_{j}(Aj≤BjA_{j}\le B_{j}),j=1...Nj=1...N。所有A,BA,B 与TT 都是非负整数(可能相等),并皆小于等于1,000,000,0001,000,000,000。

输出格式

请计算最大的可行牛-鸡配对数。

样例 #1

样例输入 #1

5 4
7
8
6
2
9
2 5
4 9
0 3
8 13

样例输出 #1

3