5179: 油漆围栏（Painting the Fence）
[Creator : ]
Description
你有一个长为 n 的栅栏，非常不幸，这些围栏都没有油漆过。围栏标号 [1, …, n]。你有 q 个粉刷匠，每个人有一个 l，r，即在 [l, r] 范围内的栅栏都可以粉刷。
现在你只能雇佣 q-2 个人，求最长的粉刷范围。
现在你只能雇佣 q-2 个人，求最长的粉刷范围。
Input
第一行包括两个整数 n 和 q （3 ≤ n, q ≤ 5000）
接着是 q 行，每行包括两个整数 li 和 ri，表示第 i 个油漆匠负责的区域（1 ≤ li ≤ ri ≤ n）。
接着是 q 行，每行包括两个整数 li 和 ri，表示第 i 个油漆匠负责的区域（1 ≤ li ≤ ri ≤ n）。
Output
一个整数，雇佣了 q-2 个人后，最长的粉刷范围。
Sample 1 Input
7 5
1 4
4 5
5 6
6 7
3 5
Sample 1 Output
7