P1209 [USACO1.3] Barn Repair

On a dark and stormy night, the roof and doors of Farmer John's barn were blown off. Fortunately, many cows are on vacation, so the barn is not full. The stalls are arranged in a single row, one right next to another, and cows stay in them overnight. Some stalls are occupied, others are empty. All stalls have the same width. Since the doors were lost, Farmer John must quickly put up new wooden boards in front of the stalls. His new lumber supplier can provide boards of any length he wants, but, being stingy, can supply only a limited number of boards. Farmer John wants to minimize the total length of the boards he buys. Given $m, s, c$ — the maximum number of boards, the total number of stalls, and the total number of cows — and the index of the stall occupied by each cow, compute the minimal total length of boards required to block all stalls that contain cows. Each board covers a consecutive range of stalls.

One line with three integers $m, s, c$, as described above. Then $c$ lines follow, each containing one integer, the index of a stall that contains a cow.

Output a single line with one integer, the minimal total length of boards required.

Constraints For $100\%$ of the testdata, $1 \le m \le 50$, $1 \le c \le s \le 200$. USACO Training Section 1.3. Translated by ChatGPT 5