#8053. 算法提高 线段和点 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: 匿名

题目描述

有n个点和m个区间,点和区间的端点全部是整数,对于点a和区间[b,c],若a>=b且a<=c,称点a满足区间[b,c]。
求最小的点的子集,使得所有区间都被满足。

输入格式

第一行两个整数n m
以下n行 每行一个整数,代表点的坐标
以下m行 每行两个整数,代表区间的范围

输出格式

输出一行,最少的满足所有区间的点数,如无解输出-1。

样例

样例输入1

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

样例输出1

2

数据范围与提示

1<=n,m<=10000
0<=点和区间的坐标<=50000