Farmer John 要为排成一列的 $N$ 头牛（$(1 \le N \le 200,000)$）拼一张全景照片，牛照常编号为 $1..N$。他拍了 $M$ 张照片（$(1 \le M \le 100,000)$），每张覆盖一段连续的牛：照片 $i$ 包含牛 $a_i$ 到 $b_i$，含两端。所有照片不一定覆盖每头牛。

拍照后 FJ 发现每张照片恰好有一头带斑点的牛！他知道牛群中有些牛带斑点，但从没数过。根据照片，求牛群中带斑点的牛最多可能有多少头。若无法给牛分配斑点，使结果与照片一致，输出 $-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$ 必须有一头带斑点。选择其中任意一头，也满足前两张照片。

出题人：Brian Dean，2013