Egyptian Teleporter Race

You are competing in a race across Egypt along a straight road running from west to east. You start at the very west end and must always proceed eastward on foot. Along the road there are (N) teleporters. Each teleporter has two endpoints located at distinct positions strictly between the start and the finish. When you reach either endpoint of a teleporter, it immediately teleports you to its other endpoint. (Note that depending on which endpoint you reach, the teleporter may send you either eastward or westward.) After every teleportation you continue eastward, and you cannot avoid any teleporter endpoint that lies on your path.

Every time you are teleported you receive 1 point. The goal is to collect as many points as possible before reaching the finish. In order to increase your score, you are allowed, before the race begins, to add up to (M) new teleporters. You may choose the endpoints of these new teleporters arbitrarily (even non‐integer positions) as long as no endpoint coincides with any other endpoint (including endpoints of the existing teleporters) and these endpoints lie strictly between the start and finish. It is guaranteed that no matter how you add these teleporters, you can always reach the finish.

An important observation is that in the base race (with no added teleporters) you will trigger each teleporter exactly once (since, on the way east, you always encounter the western endpoint first). However, by adding a teleporter suitably you can force a cycle (or loop) in a specific segment of the race such that the teleporters in that segment get used an extra time. For example, by adding a new teleporter that diverts you from before a teleporter’s lower endpoint to a point between its two endpoints, you can cause that teleporter to be used in reverse order – yielding an extra activation. In an optimal strategy, you may design a cycle for some teleporters so that one teleporter, if cycled individually, yields 3 teleports (1 from the base run and 2 from the cycle). Thus if you choose to “cycle” a teleporter then its total contribution becomes 3 points rather than 1, an extra of 2 points. Since one cycle uses one new teleporter and the cycles must be disjoint along the road, the maximum number of teleporters you can independently cycle is (\min(M, N)).

Hence the maximum score you can obtain is computed as follows. In the base run, you get (N) points (one per teleporter). Then, for each teleporter you are able to cycle (and you can cycle at most (\min(M,N)) teleporters), you get an extra 2 points. In other words, the answer is [ \text{Answer} = N + 2\cdot\min(M,N). ]

Your task is to write a program that, given (N) and (M) along with the positions of the endpoints for the (N) teleporters, computes the maximum score you can obtain by optimally adding up to (M) new teleporters.

inputFormat

The first line contains two integers \(N\) and \(M\) (where \(0 \le M\le N\)). Each of the next \(N\) lines contains two real numbers representing the positions of the two endpoints of a teleporter. (It is guaranteed that no two endpoints share the same position.)

You may assume that all endpoints lie strictly between the start and the finish. The positions of the endpoints of the new teleporters are not given since you can choose them arbitrarily.

outputFormat

Output a single integer — the maximum score that can be achieved.

Note: The maximum score is given by \(N + 2 \cdot \min(M, N)\).

sample

1 0
2 5

1