样例下载

【题目描述】

参加完 CXP 后，N 名同学合影留念。他们排成一排，从左到右编号为 1 ~ N。

老师给同学们拍照。由于队伍太长，一张照片可能无法把所有同学全部拍进去。

于是老师拍了 M 张照片，第 i 张照片包含了编号为 $L_i$ ~ $R_i$ 的连续的若干位同学。这些照片不一定把每一位同学都拍了进去。

拍完照后，老师发现了一件有趣的事情：每张照片中都有且仅有一名女生。

问：N 名同学中，最多可能有多少名女生？

如果无解，输出 -1。

【输入格式】

第一行：两个整数 N M

接下来 M 行，每行两个整数：$L_i, R_i$

【输出格式】

一行，一个整数

【样例输入1】

6 3 
2 5 
3 6 
4 5

【样例输出1】

2

【样例输入2】

6 3 
1 2 
3 4 
1 5

【样例输出2】

-1

【数据范围】

全部测试点满足：$1 ≤ N ≤ 2×10^5， 1 ≤ M ≤ 10^5, 1 ≤ L_i ≤ R_i ≤ N$

测试点1：1 ≤ N ≤ 10， 1 ≤ M ≤ 10

测试点2：1 ≤ N ≤ 100， 1 ≤ M ≤ 100

测试点3：1 ≤ N ≤ 1000， 1 ≤ M ≤ 1000

测试点4：1 ≤ N ≤ 1000， 1 ≤ M ≤ 2000

测试点5-6：1 ≤ N ≤ 2000， 1 ≤ M ≤ 1000

测试点7-10：1 ≤ N ≤ $2×10^5$， 1 ≤ M ≤ $10^5$