题目背景

一条笔直的公路，从第 1 个灯柱位置一直排到第 N 个灯柱位置，需要被路灯照亮。市政部门提供了 n 种可供选择的路灯安装方案，第 i 种方案能在公路上照亮一段连续的范围 [l_i, r_i]。

每盏灯只能选择安装或者不安装。市政部门希望用尽量少的路灯，让整条公路（从位置 1 到位置 N）都被照亮。

题目描述

给定公路范围 [1, N] 和 n 种路灯的照明范围 [l_i, r_i]，选出最少的方案，使得这些范围的并集完全覆盖 [1, N]。输出最少需要的灯数；如果无论怎么选都照不满整条路，输出 `-1`。

输入格式

第一行两个整数 N, n。

接下来 n 行，每行两个整数 l, r，表示一种方案的照明范围。

输出格式

一个整数，表示最少需要安装的路灯数量；若照不满整条路，输出 `-1`。

输入输出样例

10 4
1 4
3 7
6 10
8 10

3

样例 1 解释

选 [1,4]、[3,7]、[6,10]，并集为 [1,10]，正好照满整条公路，共 3 盏；用 2 盏照不满。

说明/提示

1 ≤ N ≤ 10^9

1 ≤ n ≤ 10^5

1 ≤ l < r ≤ 10^9

路灯照明范围可以超出公路 [1, N]；无解输出 `-1`