배고픈 여우

시간 제한2초메모리 제한512 MB

요약

크래커 온도들과 물의 온도가 주어질 때, 먹는 순서와 물 마시는 시점을 정해 인접한 온도 차의 합의 최솟값과 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬, 수학
정답자: 아직 제출이 없습니다

문제

애완 여우의 저녁 시간이다. 저녁 식사는 크래커 $N$ 개이고, $i$ 번째 크래커의 온도는 $T_i$ 도(섭씨)이다. 여우 곁에는 큰 물그릇도 하나 있는데, 물의 온도는 $W$ 도이다.

여우는 먼저 물을 한 모금 마신 뒤 식사를 시작한다. 크래커를 하나 먹을 때마다 그 크래커의 맛은 크래커의 온도와 여우가 직전에 먹거나 마신 것의 온도의 차의 절댓값이다. 직전에 먹거나 마신 것은 바로 앞에 먹은 크래커일 수도 있고 물 한 모금일 수도 있으며, 둘 중 더 최근에 먹거나 마신 쪽을 기준으로 한다. 여우는 원할 때 언제든 물을 마실 수 있고, 크래커는 어떤 순서로든 먹을 수 있다.

여우가 먹고 마시는 순서에 따라 먹은 크래커들의 맛의 합이 달라질 수 있다. 이 합의 최솟값과 최댓값을 구하여라.

입력

첫째 줄에 크래커의 개수 $N$ 과 물의 온도 $W$ 가 주어진다. ( $1 \le N \le 100\,000$ , $0 \le W \le 10^9$ )

다음 $N$ 개의 줄에는 한 줄에 하나씩 정수 $T_i$ 가 주어진다. $T_i$ 는 $i$ 번째 크래커의 온도이다. ( $0 \le T_i \le 10^9$ )

출력

여우가 느낄 수 있는 맛의 합의 최솟값과 최댓값을 차례로 공백으로 구분하여 한 줄에 출력한다.

예제2

예제 1
입력
```
3 20
18
25
18
```
예상 출력
```
7 16
```
예제 2
입력
```
2 0
10
1
```
예상 출력
```
10 19
```