题目描述

农夫约翰决定给站在一条线上的N(1 <= N <= 200,000)头奶牛制作一张全家福照片，N头奶牛编号1到N。

于是约翰拍摄了M(1 <= M <= 100,000)张照片，每张照片都覆盖了连续一段奶牛：第i张照片中包含了编号$a_i$ 到 $b_i$的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。

在拍完照片后，约翰发现了一个有趣的事情：每张照片中都有且仅有一只身上带有斑点的奶牛。约翰意识到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。 根据照片，请你帮约翰估算在他的牛群中最多可能有多少只斑点奶牛。如果无解，输出“-1”。

输入格式

第1行：两个整数N和M

第2..M+1行：第i+1行包含 $a_i$ 和 $b_i$

输出格式

农场中可能存在的斑点奶牛的最大数量，若无解则输出-1

输入输出样例 #1

输入 #1

5 3 
1 4 
2 5 
3 4

输出 #1

1

说明/提示

样例中有5头奶牛和3张照片。第一张照片包含奶牛1到4，依此类推。

从最后一张照片我们知道，奶牛3或奶牛4中必须有一头是斑点奶牛。选择其中任意一头，都能满足前两张照片的条件。