시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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

출력

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

예제 입력 1

2 10
25 50

예제 출력 1

55

예제 입력 2

5 2
4 5 6 7 8

예제 출력 2

14