Задача №1906. Распил брусьев
Вам нужно распилить деревянный брус на несколько кусков в заданных местах. Распилочная компания берет \(k\) рублей за распил одного бруска длиной \(k\) метров на две части.
Понятно, что различные способы распила приводят к различной суммарной стоимости заказа. Например, рассмотрим брус длиной 10 метров, который нужно распилить на расстоянии 2, 4 и 7 м, считая от одного конца. Это можно сделать несколькими способами. Можно распилить сначала на отметке 2 м, потом 4 и, наконец, 7 м. Это приведет к стоимости 10+8+6=24, потому что сначала длина бруса, который пилили, была 10 м, затем она стала 8 м, и, наконец, 6 м. А можно распилить иначе: сначала на отметке 4 м, затем 2, затем 7м. Это приведет к стоимости 10+4+6=20, что лучше.
Определите минимальную стоимость распила бруса на заданные части.
Первая строка входных данных содержит целое число \(L\) (2≤\(L\)≤\(10^6\)) - длину бруса и целое число \(N\) (1≤\(N\)≤100) - количество распилов. Во второй строке записано \(N\) целых чисел \(С_i\) (0<\(C_i\)<\(L\)) в строго возрастающем порядке - места, в которых нужно сделать распилы.
Выведите одно натуральное число - минимальную стоимость распила.
10 3 2 4 7
20