410253: GYM103993 H Report Preparation

Monocarp is a student. There are $$$n$$$ other students in his group at the university.

The Linguistics lecturer told the students to prepare a report based on a book which consists of $$$m$$$ pages. Pages of the book are numbered from $$$1$$$. The group of students will be prepared for the report if every page of the book is read by at least one student.

The $$$i$$$-th student from $$$n$$$ of Monocarp's groupmates (excluding Monocarp himself) has read several pages of the book, from the page $$$a_i$$$ to the page $$$b_i$$$ inclusive ($$$a_i \le b_i$$$).

Monocarp will read several consecutive (without skips) pages of the book — he thinks that it will allow him to prepare better. You have to calculate the minimum number of pages he has to read so that the group is prepared for the report (i. e. so that every page is read by at least one student).

Note that if every page of the book is already read by at least one student, Monocarp won't read anything.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le m \le 10^{9}$$$) — the number of students (excluding Monocarp) and the number of pages in the book, respectively.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le b_i \le m$$$) — the first and the last page in the part of the book which was read by the $$$i$$$-th student. So, the $$$i$$$-th student has read all pages from the $$$a_i$$$-th one to the $$$b_i$$$-th one inclusive.

Print one integer — the minimum number of pages Monocarp has to read so that every page is read by at least one student. If Monocarp doesn't have to read anything, print $$$0$$$.

2 6
1 2
5 6

2

3 10
2 7
5 8
9 9

10

2 15
1 13
4 15

0

In the first example, Monocarp has to read the third page and the fourth page, and the group will be prepared for the report.

In the second example, neither the first page nor the last page has been read. Since Monocarp cannot skip pages while reading, he has to read all $$$10$$$ pages of the book.

In the third example, Monocarp doesn't have to read anything, since each page is already read by some other student.