13471347 SUSTech Online Judge
Problem 1347 --[Medium] Relay

1347: [Medium] Relay

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 989  Solved: 272
[Submit][Status][Web Board]

Description

It is September now, and thousands of freshmen entered S University. In order to welcome them and help them get familiar to the campus, S University is going to hold a relay race on a straight runway around the campus.

The runway passes by \(n\) trees (the first tree is at position \(0\)) and the finish line is at position \(L\). There are \(m\) freshmen joining in the race. Before the relay race starts, each of the racer should be assigned to the place of one of the trees, and there should not be two racers being assigned to the same tree. What's more, the first racer should be assigned to the place of the first tree. Then, the race starts, and every racer runs ahead to the next racer.

Since CC is strong, she runs the longest distance among the freshmen (so the distance every racer runs should be less than or equal to CC's distance). Given the positions of the trees, do you know what is the minimum distance CC may run?

Input

There is only one test case.

The first line contains three integers \(n (1\leq n\leq 10^5), m(1\leq m\leq n), L (1\leq L\leq 10^9)\), indicating the number of trees, the number of freshmen, and the position of the finish line.

The second line contains \(n\) integers \(p_1, p_2, ... p_n (0\leq p_i< L; \space p_1=0; \space p_i<p_{i+1})\), indicating the positions of the trees.


Output

Output the answer in one line.

Sample Input

4 3 25
0 2 11 18

Sample Output

11

HINT

Source

 

[Submit][Status]