CF1132C Painting the Fence

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.