19995번 - Перетягивание каната 다국어

В 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$) --- длины имеющихся кусков каната.

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