你有一个由 $$$n$$$ 部分组成的长栅栏。不幸的是,它没有上漆,所以你决定雇佣 $$$q$$$ 画家来给它上漆。第 $$$i$$$ 个画家将绘制所有 $$$x$$$ 部分,使得 $$$l_i \le x \le r_i$$$。
不幸的是,您的预算很紧张,因此您可能只雇用 $$$q - 2$$$ 画家。显然,只有您雇用的油漆工才会做他们的工作。
如果您最佳地选择 $$$q - 2$$$ 画家,则您希望最大化绘制部分的数量。如果至少有一名画家绘制了某个部分,则该部分被视为已绘制。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$3 \le n, q \le 5000$$$) — 分别是可雇用的部分数量和油漆工数量。
接下来是 $$$q$$$ 行,每行描述一位画家:$$$i$$$ 第行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$)。
输出
打印一个整数 - 如果您雇用 $$$q - 2$$$ 油漆工,则绘制部分的最大数量。
示例
输入 #1
7 5 1 4 4 5 5 6 6 7 3 5
输出 #1
7
输入 #2
4 3 1 1 2 2 3 4
输出 #2
2
输入 #3
4 4 1 1 2 2 2 3 3 4
输出 #3
3