Minimize Board Length for Cow Stalls

On a dark and stormy night, Farmer John's barn has suffered damage as its roof and door were blown away. Fortunately, many cows are on vacation, so the barns are not fully occupied. The barns are arranged in a single line, each having the same width. Some barns contain cows, while others are empty. With the loss of the door, Farmer John must quickly cover all barns that contain cows by installing new boards. His new supplier can provide boards of any length, but only up to m boards can be purchased.

Given three integers m, s, and c representing the maximum number of boards available, the total number of barns, and the total number of cows respectively, followed by the list of barn numbers where each cow is located, your task is to determine the minimum total length of boards required to cover all the barns that contain cows.

You may cover some empty barns as necessary. A board covering a contiguous range of barns from barn l to barn r has a length of \( r - l + 1 \). Initially, if we use one board to cover all cow-occupied barns (from the leftmost to the rightmost), the length will be \( L = a_{last} - a_{first} + 1 \). By removing the largest gaps between consecutive cow-occupied barns, you can reduce the total board length. Specifically, if you can use up to m boards, you may choose to break the initial continuous interval into m segments by excluding the m-1 largest gaps (each gap measured as the number of barns between consecutive occupied barns minus 1).

The formula for the minimum total board length is:

[ \text{Minimum Length} = \left(a_{last} - a_{first} + 1\right) - \sum_{i=1}^{m-1} g_i, ]

where \( g_i \) are the m-1 largest gaps between consecutive occupied barns.

inputFormat

The first line contains three integers m, s, and c separated by spaces:

• m: The maximum number of boards you can use.
• s: The total number of barns (numbered consecutively).
• c: The number of cows.

The next c lines each contain a single integer representing the barn number where a cow is located.

outputFormat

Output a single integer, the minimum total board length required to cover all barns that contain cows.

sample

3 50 8
2
5
6
7
11
12
16
17

10