공항버스

Taiwan에서 열리는 IOI 2014을 준비하던 중, 주최 측은 모든 참가 팀을 공항에서 호텔까지 수송하기에는 버스가 턱없이 부족하다는 사실을 깨달았다. 버스를 단 한 대밖에 예약하지 못했기 때문이다. 하지만 문제는 버스의 수용 인원이 아니라, 모든 팀이 공항에서 너무 오래 기다리게 하고 싶지 않다는 점이다. 그렇지 않으면 참가자들이 초조해하고 짜증을 낼 수 있으며, 당연히 주최 측은 이를 최대한 피하고 싶어 한다.

버스에는 임의의 수의 팀이 탈 수 있으며(버스는 엄청나게 크다), 공항에서 호텔까지 이동하는 데 정확히 $K$분이 걸리고, 반대 방향으로도 같은 시간이 걸린다. 팀들이 버스에 타거나 내리는 데에는 시간이 전혀 걸리지 않는다(버스에는 엄청나게 큰 문이 있다). 처음에 버스는 공항 밖에 주차되어 있다.

따라서 $N$개 팀의 도착 일정이 주어질 때, 모든 팀의 총대기 시간, 즉 도착 시각부터 버스 출발 시각까지의 시간(분)의 합을 가능한 한 작게 만들고자 한다. 버스 출발 일정을 최적으로 계획할 때 가능한 최소 대기 시간을 계산한다.

예제

첫 번째 예제에서는 세 그룹이 도착하며, 호텔까지 이동하는 데 10분이 걸린다. 최적의 방법은 2분과 4분에 도착하는 그룹들을 기다렸다가(이로 인해 마지막 그룹에는 2분의 대기 시간이 발생한다) 버스로 출발시키는 것이다. 4 + 10 + 10분 후 버스가 호텔에서 돌아오므로, 25분에 도착하는 그룹은 전혀 기다릴 필요가 없다. 따라서 답은 2분이다.

채점

여러 테스트 케이스 그룹으로 여러분의 풀이를 테스트한다. 한 그룹에서 점수를 받으려면 해당 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ | $13$ | $1 \leq N, K \leq 15$

$2$ | $18$ | $K=1$

$3$ | $19$ | $1 \leq N \leq 100$

$4$ | $23$ | $1 \leq N \leq 1000$

$5$ | $27$ | 추가 제한 없음.

입력의 첫째 줄에는 팀의 수와 호텔로 이동할 때 및 공항으로 돌아올 때 각각 걸리는 시간(분)을 나타내는 정수 $N$과 $K$ ($1 \leq N \leq 10^5, 1 \leq K \leq 100$)가 주어진다. 둘째 줄에는 각 팀이 도착하는 시각(분)을 나타내는 $N$개의 정수가 주어진다. 각 시각은 $1$ 이상 $10^9$ 이하인 정수이다.

버스 출발 일정을 최적으로 계획했을 때 모든 팀의 대기 시간의 합을 나타내는 수 하나를 출력한다.