Productivity improvement

ACME Inc. rebuilt its factory to raise productivity. The factory has $p$ production lines that are independent and identical, and each line gets some workers.

Machines do all of the work, so the production rate is the same no matter how many workers stand at a line. Safety rules allow a line to run only while every worker assigned to it is on duty. The productivity of a line is therefore the length of the time span in which all of its workers are at work together. To keep the workers proud of their line, the productivity of every line must be greater than 0.

Labor law forbids ACME from firing anyone, so all $n$ workers have to be assigned to a line, and no line may be left empty. The productivity of the factory is the sum of the productivities of the $p$ lines. What is the largest productivity the new factory can reach?

The first line contains the number of workers $n$ and the number of production lines $p$ ($1 \le p \le n \le 200$).

Each of the next $n$ lines contains the arrival time $a$ and the leaving time $b$ of one worker ($0 \le a < b \le 100\,000$).

At least one valid assignment is guaranteed to exist.

Print the maximum productivity of the factory on one line.