墙长为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.