- Prepare
- Algorithms
- Dynamic Programming
- Hard Disk Drives

# 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.