Can anyone just say how to solve this problem. I am not asking for code just a way to solve.

Question:

There is are **m** cabins numbered from 1 to m where **n** cabins are broken. You are provided with infinitely long tape which you are allowed to cut only **k** times. The task is to cover all the broken cabins with minimum length of tape used. You are provided with broken cabin positions, you are also allowed to cover non-broken cabins, and it is possible that some pieces of tape will overlap.

Input Format

First line contains three inputs n, m and k where n is number of cabins broken, m is total number of cabins, and k is number of tape pieces to be cut.

Second line contains n integers b1, b2, b3 ...... bn represents positions of broken cabins in increasing order.

Output Format

print minimum total length of the pieces.

Example:

Input

4 100 2

20 30 75 80

Output

17

Explanation:

4 broken cabins, you need to cover broken cabins with 2 pieces of tape.

cabins - Bold numbers are broken cabins

1.......**20**........**30**....................**75**.......**80**........100

..........-----11-----___________ -----6-----_______

length of tape used to cover cabin 20 and 30 is 11

length of tape used to cover cabin 75 and 80 is 6

so total length is 17

If k=4 that means only 1 meter tape of 4 pieces are required to cover cabins 20, 30, 75, and 80 So the total length required is 4.

I tried in many different ways by taking gaps between the broken cabins and by sorting them, but some cases are not getting solve. Please anyone just suggest algorithm to solve this problem. It is not urgent so you can take time to solve.