Teleporters#279
You are participating in a competition to cross Egypt from west to east along a straight segment. Initially, you are located at the west endpoint of the segment. The rules require you to move only along the segment and only eastward.
There are teleporters on the segment. Each teleporter is defined by two points on the segment. Whenever you reach one of these points, you are immediately transported to the other point of the teleporter (note that, depending on which endpoint you reach, teleportation may move you to the east or west of your current location). After teleportation, you must continue moving eastward along the segment. You cannot avoid any teleporter endpoint that is on your way. No two teleporter endpoints are at the same position. All endpoints are strictly between the start and end of the segment.
Each time you are teleported, you earn one point. The objective is to earn as many points as possible. To maximize your score, before your journey starts, you are allowed to add up to new teleporters to the segment. You also earn points by using the new teleporters.
You can position the endpoints of the new teleporters wherever you wish (even at non-integer positions), as long as you do not place them at positions already occupied by other teleporter endpoints. That is, all endpoints of all teleporters must be at distinct positions. New teleporter endpoints must also lie strictly between the start and end of the segment.
It is guaranteed that, no matter how you add the teleporters, you can always reach the end of the segment.
The input consists of:
• The first line contains an integer (1 \leq N \leq 1\,000\,000), the number of teleporters initially present on the segment.
• The second line contains an integer (1 \leq M \leq 1\,000\,000), the maximum number of new teleporters you may add.
• Each of the next lines describes a teleporter. The -th of these lines contains two integers W_i and E_i (1 \leq W_i < E_i \leq 2\,000\,000), the positions of the west and east endpoints of the teleporter, respectively, measured from the beginning of the segment.
No two endpoints coincide. The segment starts at position and ends at position .
Output a single integer: the maximum number of points you can earn.
Example 1