29487번 - Super Massive Black Hole 다국어

Джон --- потомственный производитель черных дыр. Уже не одно поколение завод его семьи исправно производит черные дыры любой массы.

Сегодня на завод Джона поступил заказ --- через $D$ дней он должен отдать заказчику $n$ черных дыр. При этом черные дыры должны иметь массы $w_i$.

Из соображений безопасности каждый день Джон может производить не более одной черной дыры. К сожалению черные дыры нельзя хранить, так как они очень агрессивны и почти сразу начинают уничтожать все вокруг себя.

Но у Джона есть специальная машина времени для перемещения черных дыр (по неизвестным причинам машина способна перемещать только черные дыры). Однако использование этой машины стоит много денег, а именно, чтобы переместить черную дыру массой $w$ на один день вперед или назад, Джону приходится заплатить $w$ условных единиц. Естественно Джон хочет тратить как можно меньше условных единиц на перемещение черных дыр. Помогите Джону.

В первой строке входного файла два целых числа $n$ и $D$ ($1 \le n \le 100$, $0 \le D \le 1000$). Во второй строке $n$ целых чисел $w_i$ ($1 \le w_i \le 1000$) --- массы черных дыр.

В выходной файл одно число --- минимальное число условных единиц, необходимое на выполнение заказа. Напоминаем, что все черные дыры необходимо отдать заказчику в день $D$, а начать их производить Джон может только с сегодняшнего дня. Сегодняшний день имеет номер ноль.

В первом примере одно из оптимальных решений выглядит следующим образом: в нулевой день производится первая черная дыра, в первый --- третья и во второй --- вторая. Таким образом суммарные затраты составляют $1 \cdot 1 + 3 \cdot 0 + 2 \cdot 1 = 3$.