SOLVE

LATER

The lone wolf dies, but the pack survives

/

Nymeria wants to join a wolf pack to protect herself during the winter that is fast approaching. There's a wolf pack in Riverlands that allows wolves to join their pack if they are able to solve a question. Help Nymeria join the pack by solving the question.

You are provided with an array of **N** integers and a number **Y**, and asked to perform exactly **D** operations on it. Operations are such that you have to :

1. First subtract an integer **X** from each element of the array

2. Check if any of them becomes negative or zero then discard them

3. Add an integer Y to the remaining ones

Repeat these 3 steps **D** times such that you are left with an empty array at last.

Your task is to choose the smallest possible integer value of **X** to perform the above mentioned operations on the array.

*CONSTRAINTS :*

1 <= N <= 10^{6}

1 <= A_{i}, Y, D <= 10^{6}

**INPUT FORMAT :**

First line of each input dataset will contain 3 space separated integers N, D and Y.

Next line will contain N space separated array elements.

**OUTPUT FORMAT :**

Output the smallest possible value X can take.

Explanation

Here we have D = 2 and Y = 2

Initially we have the array as : 2 1 5 3 6

suppose we choose X = 4

After 1st operation we have :

-2 -3 1 -1 2 => discarding 1st, 2nd and 4th element => 1 2 => add Y to it => 3 4

After 2nd operation we are left with :

-1 0 => discard all => empty array

So X = 4 is a possible answer.

Check it youself for more values of X, you will see that it is the smallest possible value for X.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...