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