Lifeguards Coverage Optimization

Farmer John has opened a swimming pool for his cows and hired N lifeguards. The pool is open daily from time \(0\) until \(10^9\). Each lifeguard works a shift given by a contiguous time interval \([s,e)\) (note that if a lifeguard works from \(t=4\) to \(t=7\) she covers 3 units of time). However, due to budget constraints, John must fire exactly \(K\) lifeguards. Your task is to choose the \(N-K\) lifeguards to keep such that the total time covered (an instant is covered if at least one lifeguard is on duty) is maximized.

Input Format: The first line contains two space‐separated integers \(N\) and \(K\). Each of the next \(N\) lines contains two space‐separated integers \(s\) and \(e\), representing the start and end time of a lifeguard's shift.

Output Format: Output a single integer giving the maximum amount of time that can be covered by the remaining lifeguards after firing exactly \(K\) of them.

Note: Shifts may overlap. The union of intervals is counted (overlapping time is only counted once).

inputFormat

The first line contains two integers \(N\) and \(K\) (the number of lifeguards and the number to fire). Each of the next \(N\) lines contains two integers \(s\) and \(e\) (start and end time of a shift).

For example:

3 1
0 4
2 7
5 9

outputFormat

Output a single integer: the maximum covered time possible after firing exactly \(K\) lifeguards.

sample

3 1
0 4
2 7
5 9

8