Productivity improvement

Time limit2sMemory limit256 MB

Summary

Partition all workers into exactly p nonempty lines to maximize the sum of each line's common overlapping work time.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Intervals
Solved: No attempts yet

Problem

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?

Input

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.

Output

Print the maximum productivity of the factory on one line.

Examples3

Example 1
Input
```
4 2
1 3
1 5
4 6
2 7
```
Expected output
```
4
```
Example 2
Input
```
1 1
0 100000
```
Expected output
```
100000
```
Example 3
Input
```
4 4
0 1
1 2
2 3
3 4
```
Expected output
```
4
```