P4686 [IOI 2008] Teleporters

You are taking part in a race that goes from west to east along a straight route across Egypt. At the start, you are at the westernmost end of this straight route. According to the rules, you must always move east along this straight route. There are $N$ teleporters on this route. Each teleporter has two endpoints. Whenever you reach one of the two endpoints of a teleporter, it immediately teleports you to the other endpoint (note that depending on which endpoint you are at, the teleporter may send you eastward or westward). After being teleported to the other endpoint, you must continue moving east along the route; you cannot avoid any teleporter endpoints that lie on your path. It is guaranteed that no teleporter has both endpoints at the same position. All endpoints lie strictly between the start and the finish of the route. Each time you are teleported, you gain $1$ point. The goal of the race is to gain as many points as possible. To maximize your score, you are allowed to add up to $M$ new teleporters on this route before the race starts. You can also gain points by using these new teleporters. You may place the endpoints of these new teleporters at any positions (even at non-integer coordinates), as long as those positions are not already occupied by another endpoint. In other words, all teleporter endpoint positions must be unique. Likewise, the endpoints of the new teleporters must also lie strictly between the start and the finish of the route. It is guaranteed that no matter how you add these teleporters, you will always be able to reach the finish of the race route. Write a program that, given the endpoints of the $N$ existing teleporters and the number $M$ of new teleporters you may add, computes the maximum score you can obtain.

Your program must read the following data from standard input: - Line $1$ contains an integer $N$, the number of teleporters initially on the route. - Line $2$ contains an integer $M$, the maximum number of new teleporters you may add. - The next $N$ lines each describe one teleporter. Line $i$ describes the $i$-th teleporter and contains two integers $W_i$ and $E_i$, which give the distances from the start of the route to the two endpoints of that teleporter. For these teleporters, no two endpoints are at the same position. The start of the race route is at position $0$, and the finish is at position $2\,000\,001$.

Your program must write one line to standard output containing a single integer, the maximum score you can achieve.

### Explanation for Sample 1  The left figure above shows a race route with $3$ teleporters initially. The right figure shows the same route after adding one new teleporter with endpoints at $0.5$ and $1.5$. After adding the new teleporter shown above, your journey is as follows: - You start at position $0$ and move east. - You reach the teleporter endpoint at $0.5$ and are teleported to the other endpoint at $1.5$ (you gain $1$ point). - You continue moving east and reach the teleporter endpoint at $2$; you are teleported to the other endpoint at $3$ (you now have $2$ points in total). - You reach the teleporter endpoint at $4$ and are teleported to the other endpoint at $1$ (you now have $3$ points in total). - You reach the teleporter endpoint at $1.5$ and are teleported to the other endpoint at $0.5$ (you now have $4$ points in total). - You reach the teleporter endpoint at $1$ and are teleported to the other endpoint at $4$ (you now have $5$ points in total). - You reach the teleporter endpoint at $10$ and are teleported to the other endpoint at $11$ (you now have $6$ points in total). - You continue until you reach the finish of the race, ending with a total score of $6$ points. ### Constraints - For $30\%$ of the testdata, $N \leq 500$ and $M \leq 500$. - For all testdata, $1 \leq N \leq 1,000,000$, $1 \leq M \leq 1,000,000$, $1 \leq W_X < E_X \leq 2,000,000$. Translated by ChatGPT 5