该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

线段覆盖

题目描述

有一条数轴，上有$1\sim n$这个$n$个点，给定$m$个线段，从中选择一些线段，要求覆盖数轴上的每一个点，并且相交部分最少。

输入格式

第一行两个整数$n,m$，表示数轴的范围和线段的个数。

接下来$m$行，每行两个整数$l_i,r_i$，表示第$i$个线段的覆盖范围是$[l_i,r_i]$。

输出格式

一个整数，表示任选一些线段，覆盖整个数轴后最小的相交部分的长度。

如果给定的线段不足以覆盖$[1,n]$，请输出$-1$。

样例 #1

样例输入 #1

8 4
1 4
2 5
6 8
3 7

样例输出 #1

3

提示

一个方案是选择线段$[1,4]$，$[2,5]$和$[6,8]$

相交部分是$[2,4]$，总长度为$3$

注意相交多次仅算一次贡献，即如果有两个及以上线段都覆盖了区间$[l,r]$，那么区间$[l,r]$仅贡献一个$r-l+1$的长度。

对于$7\%$的数据，$n,m\leq 10$

对于另外$66\%$的数据，$n,m\leq 5000$

对于全部数据：

$1\leq n,m\leq 10^5,l_i<=r_i,l_i,r_i\in[1,n]$