정전 Batch Compilation commands

OJ시는 직선 형태의 가로수길에 총 $N$개의 가로등을 설치했다. 각 가로등의 위치는 지하철역을 기준으로 -1,000,000,000 이상 1,000,000,000 이하의 정수로 나타낼 수 있다. 한편, 모든 가로등은 자신과 $L$만큼 먼 곳까지 빛을 밝힐 수 있다. 예를 들어, 좌표가 5인 가로등이 2만큼 먼 곳까지 빛을 밝힐 수 있다면 좌표가 3~7인 곳을 밝힐 수 있다.

요즘 들어, OJ시에 전력난이 지속되어 자주 정전이 난다. 정전이 나면 가로수길이 완전히 암흑에 둘러싸이기 때문에 치안에 악영향을 끼친다. 따라서 OJ시에서 $N$개의 가로등들 중 일부를 비상용으로 전환해서 정전 시에만 켜지게 할 것이다.

평소의 조명 상태와 정전 시의 조명 상태가 균일하게 이루어져야 언제든지 시민들이 편하게 가로수길을 드나들 수 있다. 이에 따라 OJ시는 어떤 경우에도 항상 빛이 도달하는 지점의 총 길이를 최대화시키려고 한다. OJ시를 도와 무슨 가로등을 비상용으로 바꿀지 구하는 프로그램을 작성하여라.

입력 형식

첫 번째 줄에는 가로등의 수 $N$과 가로등의 조도 $L$이 주어진다.

두 번째 줄에는 $N$개의 가로등의 좌표가 공백을 사이로 두고 차례대로 주어진다.

출력 형식

가로등 중에 몇 개를 비상용으로 전환했을 때, 평상시와 비상시에 모두 빛의 영향을 받는 영역의 길이의 최댓값을 출력한다.

부분문제

모든 예제에 대해,

• $N \ge 1$
• $1 \le L \le 1, 000, 000, 000$

부분문제	점수	N	비고
1	10	≤ 15	-
2	20	≤ 1, 500	-
3	30	≤ 150, 000	모든 지역은 최대 2개의 가로등의 영향을 받는다.
4	40	≤ 150, 000	-

입력과 출력의 예

입력

6 3
-6 -2 1 3 8 15

출력

9

예제 설명

2, 4번째 가로등을 비상용으로 전환하면 된다.