OI题库

【题目描述】

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

【输入格式】

输入文件的第一行有两个空格隔开的整数：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