Approximation

Memory limit: 64 MB

Approximation of a real function by another function is a task of finding such real function that has certain properties and can be used instead of with relatively small error. Most often is expected to be simpler than in some way and it should be possible to compute its values efficiently.

We define a staircase function as a real function such that its domain can be partitioned into intervals of the form (with and being some real numbers) satisfying the property that is constant on each of these intervals. Such interval for which is constant is called a stair of the function.

For simplicity let us assume that considered functions can change values only in points with integer -coordinate (so they are constant on any interval of the form where is an integer) and the domain we are interested in is .

We are interested in approximation of a staircase function which has at most stairs by functions having at most stairs. The error of approximation that we are willing to minimize is defined as:

for some value of the parameter .

Task

Write a program which:

• reads a description of function , the number of stairs of function and number from the standard input,
• computes the best approximation of function by a staircase function having at most stairs,
• writes the error of approximation to the standard output.

Input

The first line of the input file contains three integers , and (, , ), separated with single spaces. denotes the number of stairs of function whereas denotes the maximum number of stairs of function . Each of the following lines contains one integer () - the value of at all points from the interval , where .

Remark: tests with different values of are not grouped together.

Output

The first and only line of the output file should contain one non-negative real number - the error of the best approximation of by any -stair function . The difference between the actual answer and your program's answer must not be greater than .

Example

For the input data:

6 3 1
0
3
3
2
9
0

the correct result is:

4.00

(for the correct answer would be ).

Task author: Krzysztof Duleba.