Задача DSP2

Колоди потрібно розпиляти поперек на шматки потрібної довжини. Вартість розпилу залежить від початкової довжини колоди. Наприклад колоду довжиною 10 метрів потрібно розпилити на відстані 2, 4, та 7 м, рахуючи від одного кінця. Це вдасться зробити кількома способами. Можна розрізати на поділці 2 м, потім - 4 і потім 7 м, це призведе до вартості 10+8+6=24 (спочатку колода мала довжину 10 м, після першого розпилу - 8 м, після другого 6 м). Однак можна розпилювати по-іншому - спочатку на поділці 4 м, потім - 2 м і потім 7 м. Це призведе до вартості 10+4+6=20, що, звісно, дешевше. Напишіть програму, яка визначає мінімальну вартість розпилу для будь-якої колоди заданої довжини.

Технічні умови. Програма зчитує з клавіатури ціле додатне число L<1000 - початкову довжину колоди, далі - число N<50 - кількість розпилів, які потрібно зробити, далі - N цілих додатних чисел, Ci(0<Ci<L), що задають місця, в яких потрібно зробити розпили в суворо зростаючому порядку. Програма виводить на екран мінімальну вартість розпилу даної колоди.

Приклад.

Введення> 100 3 25 50 75
Виведення> 200

Задача DSP2

Бревна нужно распилить поперек на куски нужной длины. Стоимость распиловки зависит от начальной длинны бревна. Например, бревно длиной 10 метров нужно распилить на расстоянии 2, 4 и 7 м, считая от одного конца. Это можно сделать несколькими способами. Можно распилить на отметке 2 м,потом - 4 и потом 7 м, это приведет к стоимости 10+8+6=24 ( сначала бревно имело длину 10 м, после первого распила - 8 м, после второго - 6 м). Однако можно пилить и иначе - сначала на отметке 4 м,потом - 2 и затем 7 м. Это приведет к стоимости 10+4+6=20, что, естественно, дешевле. Напишите программу, которая определяет минимальную стоимость распиловки для любого бревна указанной длины.

Технические условия. Программа считывает с клавиатуры целое положительное число L<1000 - начальную длину бревна, далее- число N<50 - количество распилов, которые нужно сделать, далее - N целых положительных чисел Cі(0<Ci<L), задающие места, в которых нужно сделать распилы в строго возрастающем порядке. Программа выводит на экран минимальную стоимость распиловки данного бревна.

Пример.

Ввод> 100 3 25 50 75
Вывод> 200