[CEOI2004]旅行

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file tri.in Output file tri.out

【题目描述】

在即将到来的放假季,许多人准备进行一场难忘的旅行。为了尽可能享受他们的旅程,每个人都希望和一些朋友组成团队。一个旅游中介提供了一些旅行线路。但每条线路都对团队人数有限制:给定了最小和最大的人数。每个团队只能选一条线路。并且,每条线路只能被一个团队选中。旅游中介向你寻求帮助。他们希望组织尽可能多的团队进行旅游。你的任务是匹配团队和旅行线路,使得匹配数目最大。

【输入格式】

输入文件的第一行有两个空格隔开的整数:n和m,1<=n,m<=400000,其中n是团队数量,m是线路数量。团队被编号为1到n,线路被编号为1到m

接下来n行描述了团队的大小,每个团队一行。第i+1行有一个整数si,即第i个团队的人数,1<=si<=10^9.

接下来m行描述了线路,每条线路一行。第n+j+1行有两个空格隔开的整数lj和uj,lj是游玩第j条线路的团队人数下限,uj是上限。1<=lj<=uj<=10^9。

【输出格式】

输出一行一个整数,即最多能游玩的团队数量。

【样例输入】

5 4
54
6
9
42
15
6 6
20 50
2 8
7 20

【样例输出】

3

【提示】

样例的一个安排方式是:

2号团走1号线路

3号团走4号线路

4号团走2号线路

【来源】

CEOI 2004 tri