help

Statement

You are given three integers N$,$M$,$ and K$.$ You have K arrows, and your goal is to destroy N targets. Each

target i has an initial hit points $($hp$)$ value of a$\_($i$).$ To destroy a target, its hp must be less than or equal to $0.$

When you shoot an arrow with power x at target i$,$ it decreases the hp of all targets with index j$>=$i by an

amount calculated as follows:

Damage to target j$=$max$(0,$M$*$x$-($j$-$i$)^(2))$

Your task is to find the minimum possible value of x such that you can destroy all targets, given that you can

choose the indices of your arrows optimally.

Input Format

The first line contains three integers N$,$M$,$ and K : the number of targets, the multiplier for the arrow

power, and the number of arrows, respectively.

The second line contains N integers a$\_(0),$a$\_(1),$dots,a$\_($N$-1)$ representing the initial hp of the targets.

Output Format

Output a single integer, the minimum value of x such that you can destroy all targets.

Constraints

Denote A$=$a$\_(0)+$a$\_(1)+$dots$+$a$\_($N$-1).$ In all test cases we have

M

Ntimes $10^(5).$

K

a$\_($i Constraints for each test case:

Sample

K$=1.$

AMK and N

Atimes $10^(6)*$MK and N

N

N

Ntimes $10^(5).$

Ntimes $10^(5).$

Example

Input

$412$

$3324$

Output

$5$

Explanation

In the example, you can destroy all targets with the following strategy:

Shoot the first arrow $($index $0)$ with power x$=5$ :

$$ Damage to target $0$:$1*5-(0-0)^(2)=5->$a$[0]=3-5=-2$

$$ Damage to target $1$:$1*5-(1-0)^(2)=4->$a$[1]=3-4=-1$

Damage to target $2$: $1*5-(2-0)^(2)=1->$a$[2]=2-1=1$

Damage to target $3$:$1*5-(3-0)^(2)=-4->$a$[3]=4-0=4$

Shoot the second arrow $($index $2)$ with power x$=5$ :

Damage to target $2$: $1*5-(2-2)^(2)=5->$a$[2]=1-5=-4$

Damage to target $3$:$1*5-(3-2)^(2)=4->$a$[3]=4-4=0$

All targets are eliminated.