Ваш дом огорожен длинным забором, состоящим из \(n\) секций. К сожалению, этот забор не покрашен, поэтому вы решили нанять \(q\) маляров, чтобы они покрасили забор. \(i\)-й маляр покрасит все секции с такими номерами \(x\), что \(l_i \le x \le r_i\).
Все бы было хорошо, но у вас достаточно денег, чтобы нанять только \(q - 2\) маляров. Очевидно, только те маляры, которых вы наняли, будут выполнять свою работу.
Вы хотите максимизировать количество покрашенных секций забора, для этого вам нужно выбрать \(q - 2\) маляров оптимальным образом. Секция будет считаться покрашенной, если ее покрасит хотя бы один маляр.
Выходные данные
Выведите одно целое число — максимально возможное количество окрашенных секций, если вы можете нанять только \(q - 2\) маляров.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 5
1 4
4 5
5 6
6 7
3 5
|
7
|
|
2
|
4 3
1 1
2 2
3 4
|
2
|
|
3
|
4 4
1 1
2 2
2 3
3 4
|
3
|