Задача №111982. Перетягивание каната
В 2086 году в программу зимней олимпиады решено было добавить соревнования по перетягиванию каната на льду. Для проведения финала соревнования организаторы нашли \(n\) кусков каната. Для повышения зрелищности соревнования решено было сделать связать некоторые из этих кусков в один как можно более длинный канат.
Когда начались работы по связыванию, выяснилось, что на узел, связывающий два куска каната между собой, уходит по \(d\) сантиметров каната с каждого из связываемых концов. Также, оказалось, что связывать так, что получающиеся узлы находятся близко друг к другу, невозможно: расстояние между соседними узлами должно быть хотя бы \(d\) сантиметров. Например, если \(d = 10\), то после связывания кусков каната длиной 25 и 50 сантиметров, получается канат длиной 55 сантиметров, в 15 сантиметрах от одного из краев которого находится узел.
До начала соревнований остается мало времени, поэтому они обратились за помощью к вам. Помогите организаторам выяснить, канат какой максимальной длины удастся получить.
В первой строке заданы числа \(n\) (\(1 \le n \le 100\,000\)) и \(d\) (\(1 \le d \le 1000\)) - количество кусков каната и длина каната, уходящая на завязывание узла.
Во второй строке заданы \(n\) чисел \(a_i\) (\(1 \le a_i \le 1000\)) - длины имеющихся кусков каната.
Выведите единственное число- максимальную длину каната, которую можно получить.
2 10 25 50
55
5 2 4 5 6 7 8
14