Товарищ Алексей поступил в университет города City N — столицы Берляндии. Алексей рассчитывал, что отец обеспечит ему квартиру в столице, однако, тот сказал, что пора сыну учиться самостоятельности. Так что живет теперь наш Алексей в университетской общаге.
В общаге есть ровно одна прямая сушилка длиной 100 сантиметров, на которой введена система координат: левый конец сушилки имеет координату 0, правый — координату 100. Всего в университете учатся n студентов. Деканат университета на время учебы дает в пользование студенту с номером i отрезок сушилки (li, ri). К сожалению, действия деканата совершенно не согласованы, поэтому выданные отрезки могут пересекаться. Из-за чего на одном участке сушилки могут сушиться несколько вещей разных людей.
Алексей не любит, когда до его вещей кто-то дотрагивается. Поэтому он заблаговременно хочет исключить любое соприкосновение его вещей с чужими. Помогите ему посчитать: на участки какой суммарной длины он может повесить свои вещи так, чтобы вещи никакого из (n - 1) оставшихся студентов не могли сушиться с вещами Алексея на этих участках? Учтите, что Алексей, как самый уважаемый студент, имеет номер 1.
Выходные данные
Выведите в одной строке единственное целое число k, равное сумме длин участков, на которых будет сушить вещи Алексей и не будет сушить никто из остальных студентов.
Примечание
Обратите внимание, что в данной задаче не имеет значения (так как ответом является длина) соприкасаются или нет вещи, лежащие на границах двух касающихся в точке отрезков (например, отрезков (0, 1) и (1, 2)).
В первом тестовом примере Алексей может сушить свои вещи на отрезке (0, 1). Тогда, его вещи не будут соприкасаться ни с вещами на отрезке (1, 6), ни с вещами на отрезке (2, 8). Длина отрезка (0, 1) равна 1.
Во втором тестовом примере Алексей может сушить свои вещи на двух отрезках (0, 1) и (5, 7). Суммарная длина этих отрезков равна 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 5
2 8
1 6
|
1
|
|
2
|
3
0 10
1 5
7 15
|
3
|