Minimizing Open Door Duration

In order to search for the legendary Avalon, the island authorities send out n expedition teams. The island has a single door to the outside world. Each team i leaves at time \(l_i\) and returns at time \(r_i\), where all these times are distinct. Normally, when a team leaves, the door automatically opens. However, if the team has been given one of the only \(k\) available keys, it can choose to close the door immediately upon departure.

When a team returns, one of the following must hold:

• If the door is already open, the team may simply enter.
• If the door is closed, the returning team must have a key to open it.

In addition, regardless of whether they have a key or not, every team may choose to close the door after entering.

The authorities want to keep the door open for as little time as possible in order to prevent any unauthorized escape from the island. Teams that do not receive a key force the door to remain open throughout their absence (i.e. from their departure to their return), while teams with a key can essentially make their open interval vanish (since they can close the door immediately on leaving and open it only momentarily upon return).

Your task is to assign keys to at most \(k\) teams in such a way that the total time the door remains open is minimized. Equivalently, if you remove the intervals corresponding to the teams with keys, you want the union length of the remaining intervals \([l_i,r_i]\) (which forces the door to be open) to be as small as possible. Compute this minimum open-door duration.

Note on decisions: A team with a key can avoid contributing to the door’s open time, while a team without a key will force the door open for the entire duration of its interval. If multiple non-key teams have overlapping intervals, the door remains open over the union of these intervals.

inputFormat

The first line contains two integers \(n\) and \(k\) (\(0 \le k \le n\)). Each of the following \(n\) lines contains two integers \(l_i\) and \(r_i\), denoting the departure and return times of team \(i\), respectively. All \(2n\) times are guaranteed to be distinct.

outputFormat

Output a single integer: the minimum total time during which the door remains open.

sample

3 1
1 6
2 4
5 8

5