We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Hard Disk Drives

Hard Disk Drives

There are pairs of hard disk drives (HDDs) in a cluster. Each HDD is located at an integer coordinate on an infinite straight line, and each pair consists of one primary HDD and one backup HDD.

Next, you want to place computers at integer coordinates on the same infinite straight line. Each pair of HDDs must then be connected to a single computer via wires, but a computer can have any number (even zero) of HDDs connected to it. The length of a wire connecting a single HDD to a computer is the absolute value of the distance between their respective coordinates on the infinite line. We consider the total length of wire used to connect all the HDDs to computers to be the sum of the lengths of all the wires used to connect HDDs to computers. Note that both the primary and secondary HDDs in a pair must connect to the same computer.

Given the locations of pairs (i.e., primary and backup) of HDDs and the value of , place all computers in such a way that the total length of wire needed to connect each pair of HDDs to computers is minimal. Then print the total length on a new line.

Input Format

The first line contains two space-separated integers denoting the respective values of (the number of pairs of HDDs) and (the number of computers).
Each line of the subsequent lines contains two space-separated integers describing the respective values of (coordinate of the primary HDD) and (coordinate of the backup HDD) for a pair of HDDs.

Constraints

Output Format

Print a single integer denoting the minimum total length of wire needed to connect all the pairs of HDDs to computers.

Sample Input

5 2
6 7
-1 1
0 1
5 2
7 3

Sample Output

13

Explanation

For the given Sample Case, it's optimal to place computers at positions and on our infinite line. We then connect the second () and the third () pairs of HDDs to the first computer (at position ) and then connect the remaining pairs to the second computer (at position ).

We calculate the wire lengths needed to connect the drives to each computer. The amount of wire needed to connect the second and third drives to the first computer is , and the amount of wire needed to connect the rest of the drives to the second computer is . When we sum the lengths of wire needed to connect all pairs of drives to the two computers, we get a total length of . Thus, we print as our answer.