| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 45 | 19 | 11 | 34.375% |
Джон --- потомственный производитель черных дыр. Уже не одно поколение завод его семьи исправно производит черные дыры любой массы.
Сегодня на завод Джона поступил заказ --- через $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,ドル а начать их производить Джон может только с сегодняшнего дня. Сегодняшний день имеет номер ноль.
3 1 1 2 3
3
3 0 100 200 500
400
В первом примере одно из оптимальных решений выглядит следующим образом: в нулевой день производится первая черная дыра, в первый --- третья и во второй --- вторая. Таким образом суммарные затраты составляют 1ドル \cdot 1 + 3 \cdot 0 + 2 \cdot 1 = 3$.