You are given N segments on the x-axis. You should partition them in at most k sets. For each set, we define its cost as the length of the intersection of the segments in the set. Find the partition that maximizes the sum of the cost of all the sets.
Input:
The first line contains the two integers N and k.
Each of the following N lines contains two integers x1 and x2 representing the end points of a segment.
Constraint:
N <= 6000
k <= N
x1 < x2 < 10^6
Can someone please help me with this problem.