Lifeguards (Platinum)

Farmer John opened a swimming pool for his cows, figuring it will help them relax and produce more milk.

To keep the pool safe he hires $N$ cows as lifeguards. Each lifeguard works one shift that covers a contiguous stretch of the day. The pool is open from time $0$ until time $10^9$ every day, so a shift is given by two integers, the time the cow starts and the time she ends. A lifeguard who starts at $t = 4$ and ends at $t = 7$ watches three units of time. The endpoints are points in time, so a point by itself has no length.

Farmer John hired $K$ more lifeguards than he can pay for, so he must fire exactly $K$ of them. A stretch of time is watched when at least one of the remaining lifeguards is on duty. Find the largest total amount of time the remaining shifts can still watch.

The first line contains $N$ and $K$ ($K \leq N \leq 100000$, $1 \leq K \leq 100$).

Each of the next $N$ lines contains the start time and the end time of one lifeguard's shift, two integers between $0$ and $10^9$. The start time is smaller than the end time. The $2N$ times in the input are all distinct. Shifts of different lifeguards may overlap.

Print on one line the largest total amount of time that can be watched after Farmer John fires exactly $K$ lifeguards.

In the first sample Farmer John should fire the lifeguard working from $1$ to $8$ and the one working from $7$ to $15$. The shift from $2$ to $14$ that remains watches 12 units of time.