줄다리기

2086년 동계 올림픽 프로그램에 얼음 위 줄다리기 경기를 추가하기로 했다. 결승전을 치르기 위해 주최측은 밧줄 조각 $n$개를 구했다. 경기의 재미를 높이기 위해 이 조각들 중 일부를 이어 붙여 가능한 한 긴 밧줄 하나를 만들기로 했다.

이어 붙이는 작업을 시작하자, 밧줄 두 조각을 연결하는 매듭 하나에 연결되는 양쪽 끝에서 각각 $d$센티미터의 밧줄이 든다는 사실이 밝혀졌다. 또한 만들어진 매듭들이 서로 가까이 있도록 연결할 수는 없다는 것도 드러났다. 이웃한 매듭 사이의 거리는 적어도 $d$센티미터여야 한다. 예를 들어 $d = 10$일 때 길이 25센티미터와 50센티미터인 밧줄 조각을 연결하면 길이 55센티미터인 밧줄이 만들어지고, 그 한쪽 끝에서 15센티미터 떨어진 곳에 매듭이 있다.

대회 시작이 얼마 남지 않아 주최측은 여러분에게 도움을 청했다. 주최측이 만들 수 있는 밧줄의 최대 길이를 구하도록 돕자.

첫째 줄에 $n$ ($1 \le n \le 100\,000$)과 $d$ ($1 \le d \le 1000$)가 주어진다. $n$은 밧줄 조각의 수, $d$는 매듭을 묶는 데 드는 밧줄의 길이이다.

둘째 줄에 $n$개의 수 $a_i$ ($1 \le a_i \le 1000$)가 주어진다. $a_i$는 가지고 있는 밧줄 조각의 길이이다.

만들 수 있는 밧줄의 최대 길이를 나타내는 수 하나를 출력한다.