Ваш дом огорожен длинным забором, состоящим из $$$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$$$ маляров.
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
