На урок истории к Зинаиде Викторовне пришло \(n\) учеников. На дом было задано \(m\) тем, но у учеников было мало времени для подготовки, поэтому \(i\)-й ученик выучил только темы с \(l_i\) по \(r_i\) включительно.
В начале урока каждый ученик держит свою руку на уровне \(0\). Учительница хочет спросить какие-то темы. Происходит это так:
- Учительница спрашивает тему \(k\).
- Если ученик выучил тему \(k\), то он поднимает руку на \(1\), а иначе опускает на \(1\).
Каждую тему Зинаида Викторовна может спросить
не более одного раза.
Определите, какая максимальная разность высот самой высокой и самой низкой руки может быть после опроса.
Обратите внимание, рука ученика может опускаться ниже \(0\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальную разность высот самой высокой и самой низкой руки, которая может быть в классе после опроса.
Примечание
В первом наборе входных данных Зинаида Викторовна может спросить темы \(5, 6, 7, 8\). Тогда рука \(2\)-го ученика будет на высоте \(4\), а \(4\)-го — на высоте \(-2\), то есть разность будет равна \(6\).
Во втором наборе можно спросить темы \(1\) и \(3\). Тогда рука \(1\)-го ученика будет на высоте \(2\), а \(3\)-го ученика — на высоте \(-2\). Значит, разность будет равна \(4\).
В третьем наборе разница высот между самой высокой и низкой рукой будет \(0\) при любом наборе спрашиваемых тем.
В пятом наборе можно спросить все темы. Тогда разность высот рук \(1\)-го и \(3\)-го учеников будет равняться \(12\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4 8
2 6
4 8
2 7
1 5
3 3
1 3
2 3
2 2
3 5
1 5
1 5
1 5
3 5
1 1
3 3
5 5
4 7
1 7
1 3
3 3
4 5
2 4
1 3
2 4
|
6
4
0
2
12
2
|