저택과 택배

면접 대비

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

요약

배달 도착 시각이 오름차순으로 주어지고 현관까지 왕복에 2M이 걸릴 때, 일부 배달만 받으면서 시간 T까지 공부실에 머무는 총 시간의 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

타로는 저택에서 혼자 살고 있다. 공부를 좋아하는 타로는 오늘도 저택 안 서재에서 공부하려고 한다. 타로는 서재가 아닌 다른 곳에서는 집중할 수 없어서 공부는 반드시 서재에서 한다.

그런데 오늘 타로 앞으로 택배가 $N$ 건 도착한다. $i$ ( $1 \leq i \leq N$ )번째 택배가 도착하는 시각은 $a\_i$ 이다. 배달원을 현관 앞에서 기다리게 하는 것은 죄송한 일이라, 타로는 택배가 도착하는 시각에는 현관에 있기로 했다. 저택은 넓어서 서재와 현관 사이를 이동하는 데 편도 $M$ 의 시간이 걸린다.

한편 타로는 가능한 한 오래 공부하고 싶어 한다. 시각 $0$ 부터 시각 $T$ 까지 타로가 서재에서 공부할 수 있는 시간의 최댓값을 구하시오.

타로는 시각 $0$ 에 서재에 있고, 시각 $M$ 보다 이른 시각에 택배가 도착하지 않으며, 시각 $T$ 보다 늦은 시각에 택배가 도착하지도 않는다. 또한 타로가 택배를 받는 데 걸리는 시간은 무시할 수 있다.

입력

각 데이터셋은 2행으로 이루어진다. 1행은 공백으로 구분된 3개의 정수 $N, M, T$ 로 이루어진다. 이 정수는 $1 \leq N \leq 100$ , $1 \leq M \leq 10{,}000$ , $1 \leq T \leq 10{,}000$ 을 만족한다. 2행은 공백으로 구분된 $N$ 개의 정수 $a\_1, a\_2, \dots, a\_N$ 으로 이루어진다. 각 $a\_i$ 는 $M \leq a\_i \leq T$ 를 만족하고, $a\_i < a\_{ i + 1 }$ ( $1 \leq i < N$ )이다.

출력

타로가 공부할 수 있는 시간의 최댓값을 나타내는 정수를 1행에 출력하시오.

예제3

예제 1
입력
```
1 1 5
3
```
예상 출력
```
3
```
예제 2
입력
```
2 1 10
2 7
```
예상 출력
```
6
```
예제 3
입력
```
2 4 10
6 8
```
예상 출력
```
2
```