Description

农夫约翰决定给站在一条线上的 $N$（$1 \le N \le 2 \times 10^5$）头奶牛制作一张全家福照片，$N$ 头奶牛编号 $1$ 到 $N$。

于是约翰拍摄了 $M$（$1 \le M \le 1 \times 10^5$）张照片，每张照片都覆盖了连续一段奶牛：第 $i$ 张照片中包含了编号 $a_i$ 到 $b_i$ 的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。

在拍完照片后，约翰发现了一个有趣的事情：每张照片中都有且仅有一只身上带有斑点的奶牛。约翰意识到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。

根据照片，请你帮约翰估算在他的牛群中最多可能有多少只斑点奶牛。如果无解，输出“-1”。

Input Format

第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含两个整数 $a_i$ 和 $b_i$。

Output Format

输出斑点牛的最大可能数量。

如果不存在可能解，则输出 $−1$。

5 3 
1 4 
2 5 
3 4 

1 

Hint

从最后一张照片可以得出奶牛 $3$ 或 $4$ 中，必须有一头斑点牛。

无论哪头是斑点牛，都能使得前两张照片得到满足。