Teleporters

You are taking part in a competition in which you must cross a straight-line segment from its west end to its east end. You start at the westmost point of the segment. By the rules of the competition you must always move along the segment, and you may only move eastward.

There are $N$ teleporters on the segment. Each teleporter has two endpoints. Whenever you reach one of its endpoints, the teleporter immediately sends you to the other endpoint. (Depending on which endpoint you reach, the teleport may move you either east or west of your current position.) After being teleported you must keep moving eastward, and you can never avoid a teleporter endpoint that lies on your path. No two endpoints ever share the same position, and every endpoint lies strictly between the start and the end of the segment.

Each time you are teleported you earn 1 point, and your goal is to earn as many points as possible. To maximize your score, before starting you may add up to $M$ new teleporters to the segment; you also earn points by using the new teleporters.

You may place the endpoints of the new teleporters at any positions you like (even non-integer coordinates), as long as no position is already occupied by another endpoint; that is, all endpoint positions must be distinct. The endpoints of the new teleporters must also lie strictly between the start and the end of the segment.

It is guaranteed that, no matter how you add the teleporters, you can always reach the end of the segment.

Given the positions of the endpoints of the $N$ teleporters and the number $M$ of new teleporters you may add, write a program that computes the maximum number of points you can earn.

• The first line contains the integer $N$, the number of teleporters initially on the segment.
• The second line contains the integer $M$, the maximum number of new teleporters you may add.
• Each of the next $N$ lines describes one teleporter. The $i$-th of these lines contains two integers $W_i$ and $E_i$ separated by a space: the distances from the start of the segment to the western and eastern endpoints of that teleporter, respectively.

No two endpoints of the given teleporters share the same position. The segment you travel on starts at position 0 and ends at position 2,000,001.

Print a single line containing one integer: the maximum number of points you can earn.

The first picture shows a segment with the three original teleporters. The second picture shows the same segment after adding a new teleporter whose endpoints are at 0.5 and 1.5.

After adding the new teleporter as shown, your journey goes as follows:

• You start at position 0, moving east.
• You reach the endpoint at 0.5 and are teleported to 1.5 (1 point).
• You keep moving east, reach the endpoint at 2, and are teleported to 3 (2 points).
• You reach the endpoint at 4 and are teleported to 1 (3 points).
• You reach the endpoint at 1.5 and are teleported to 0.5 (4 points).
• You reach the endpoint at 1 and are teleported to 4 (5 points).
• You reach the endpoint at 10 and are teleported to 11 (6 points).
• You continue until you reach the end of the segment, finishing with a total score of 6 points.

This corresponds to the first sample input (teleporters $(10,11)$, $(1,4)$, $(2,3)$ with $M = 1$), whose maximum score is 6.