Painting the Fence

### 题意描述 墙长为n，q个工人，每个工人固定粉刷一个区间，区间可能重叠，现在要去掉两个工人，求剩下q-2个工人最多粉刷多少墙。(3≤n,q≤5000 ) (1 ≤ l i ≤ r i ≤n)

You have a long fence which consists of $ n $ sections. Unfortunately, it is not painted, so you decided to hire $ q $ painters to paint it. $ i $ -th painter will paint all sections $ x $ such that $ l_i \le x \le r_i $ . Unfortunately, you are on a tight budget, so you may hire only $ q - 2 $ painters. Obviously, only painters you hire will do their work. You want to maximize the number of painted sections if you choose $ q - 2 $ painters optimally. A section is considered painted if at least one painter paints it.

The first line contains two integers $ n $ and $ q $ ( $ 3 \le n, q \le 5000 $ ) — the number of sections and the number of painters availible for hire, respectively. Then $ q $ lines follow, each describing one of the painters: $ i $ -th line contains two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ).

Print one integer — maximum number of painted sections if you hire $ q - 2 $ painters.

7 5
1 4
4 5
5 6
6 7
3 5

7

4 3
1 1
2 2
3 4

2

4 4
1 1
2 2
2 3
3 4

3