有一条长度为 $N-1$ 的数轴。目标是从数轴上的 $1$ 出发，以最短时间到达 $N$。在总共 $T$ 分钟的时间里，每一分钟都会发生一次管制。

第 $t$ 分钟的管制由两个整数 $l_t, r_t$ 给出，如果在 $t+0.5$ 分钟时你的位置 $x$ 满足 $l_t \le x \le r_t$，则立即失败。如果 $t > T$，则不会发生任何管制。

每一分钟，你可以移动到相邻的格子，或者停留在当前格子。一旦到达 $N$，即视为成功完成目标。

如果存在不失败并到达 $N$ 的方法，请输出可能的最短时间；如果不存在，请输出 -1。

输入格式

第一行给出一个整数 $N$，表示数轴的长度。$(1 \le N \le 2 \times 10^5)$

第二行给出一个整数 $T$，表示发生管制的总时间。$(1 \le T \le 2 \times 10^5)$

从第三行开始，接下来的 $T$ 行，每行给出两个整数 $l_t$ 和 $r_t$，中间用空格隔开。$(1 \le l_t \le r_t \le N)$

输出格式

输出最短时间。如果不存在，输出 -1。

样例

输入 1

4
4
2 4
1 1
2 2
3 3

输出 1

4

输入 2

5
3
2 5
3 4
1 4

输出 2

-1