Mansion and Deliveries

Interview

Time limit10sMemory limit512 MB

Summary

Deliveries arrive at sorted times; each round trip to the door costs 2M, so pick a subset of deliveries to answer while maximizing time spent in the study up to T.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Sorting, Implementation
Solved: No attempts yet

Problem

Taro lives alone in a mansion. Taro likes studying, and today he plans to study in the study inside the mansion. Taro cannot concentrate anywhere other than the study, so he always studies in the study.

On this day, however, $N$ deliveries addressed to Taro arrive. The arrival time of the $i$ -th delivery ( $1 \leq i \leq N$ ) is $a\_i$ . Taro feels bad making the courier wait at the front door, so he decides to be at the front door at the times the deliveries arrive. The mansion is large, so moving between the study and the front door takes $M$ time in each direction.

Meanwhile, Taro wants to study for as long as possible. Find the maximum total time Taro can study in the study between time $0$ and time $T$ .

Taro is in the study at time $0$ , no delivery arrives earlier than time $M$ , and no delivery arrives later than time $T$ . The time Taro takes to receive a delivery is negligible.

Input

Each dataset consists of 2 lines. The first line contains 3 integers $N, M, T$ separated by spaces. These integers satisfy $1 \leq N \leq 100$ , $1 \leq M \leq 10{,}000$ , $1 \leq T \leq 10{,}000$ . The second line contains $N$ integers $a\_1, a\_2, \dots, a\_N$ separated by spaces. Each $a\_i$ satisfies $M \leq a\_i \leq T$ , and $a\_i < a\_{ i + 1 }$ ( $1 \leq i < N$ ).

Output

Print on one line the integer representing the maximum total time Taro can study.

Examples3

Example 1
Input
```
1 1 5
3
```
Expected output
```
3
```
Example 2
Input
```
2 1 10
2 7
```
Expected output
```
6
```
Example 3
Input
```
2 4 10
6 8
```
Expected output
```
2
```