36. Распил брусьев

Не решаласьЛёгкая

Вам нужно распилить деревянный брус на несколько кусков в заданных местах. Распилочная компания берет K K рублей за распил одного бруска длиной K K метров на две части.

Понятно, что различные способы распила приводят к различной суммарной стоимости заказа. Например, рассмотрим брус длиной 10 метров, который нужно распилить на расстоянии 2, 4 и 7 м, считая от одного конца. Это можно сделать несколькими способами. Можно распилить сначала на отметке 2 м, потом 4 и, наконец, 7 м. Это приведет к стоимости 10 + 8 + 6 = 24 10+8+6=24 , потому что сначала длина бруса, который пилили, была 10 м, затем она стала 8 м, и, наконец, 6 м. А можно распилить иначе: сначала на отметке 4 м, затем 2, затем 7м. Это приведет к стоимости 10+4+6=20, что лучше.

Определите минимальную стоимость распила бруса на заданные части.

Формат ввода

Первая строка входных данных содержит целое число L L ( 2 ≤ L ≤ 1 0 6 2 \leq L \leq 10^6 ) — длину бруса и целое число N N ( 1 ≤ N ≤ 100 1 \leq N \leq 100 ) — количество распилов. Во второй строке записано N N целых чисел С i С_i ( 0 < C i < L 0 \lt C_i \lt L ) в строго возрастающем порядке — места, в которых нужно сделать распилы.

Формат вывода

Выведите одно натуральное число — минимальную стоимость распила.

Ограничения

Ограничение времени
1 с
Ограничение памяти
64 МБ

Примеры

Пример 1

Ввод
10 3
2 4 7
Вывод
20

Пример 2

Ввод
100 3
15 50 75
Вывод
200

Теги

3.5.1
Нужно войти, чтобы отправить решение.Войти