Lifeguards (Platinum)#10426
Farmer John has opened a swimming pool for his cows, figuring that it will help them relax and produce more milk.
To ensure safety, he hires cows as lifeguards, each of whom works a shift covering a contiguous interval of time during the day. For simplicity, the pool is open from time to time 10^9 every day, so each shift can be described by two integers: the times at which the cow starts and ends her shift. For example, a lifeguard who starts at time t = 4 and ends at time t = 7 covers three units of time (the endpoints denote moments in time).
Unfortunately, Farmer John has hired more lifeguards than he can afford to pay. Given that he must fire exactly lifeguards, what is the maximum amount of time that can still be covered by the shifts of the remaining lifeguards? A moment of time is considered covered if at least one lifeguard is on duty.
The first line contains two integers and k~(1 \le k \le 100, k \le n \le 10^5). Each of the next lines contains two integers s_i and t_i~(0 \le s_i < t_i \le 10^9), the start and end times of the -th lifeguard's shift. All endpoints are distinct. Shifts of different lifeguards may overlap.
Print the maximum amount of time that can still be covered after Farmer John fires lifeguards.
Example 1
Farmer John should fire the lifeguards whose shifts are and .