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

We define a staircase function as a real function such that its domain can be partitioned into intervals of the form [a, b) (with a and b being some real numbers) satisfying the property that f is constant on each of these intervals. Such interval [a, b) for which f 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 x-coordinate (so they are constant on any interval of the form (i, i+1) where i is an integer) and the domain we are interested in is [0, n).

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

[\sum_{i=0}^{n-1}\left(\left|f(i) - g(i)\right|\right)^p]

for some value of the parameter p.

Write a program which:

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

The first line of the input file contains three integers n, k and p (1 ≤ n ≤ 4 000, 1 ≤ k ≤ 100, p ∈ {1, 2}), separated with single spaces. n denotes the number of stairs of function f whereas k denotes the maximum number of stairs of function g. Each of the following n lines contains one integer y_i (0 ≤ y_i ≤ 1 000) - the value of f at all points from the interval [i-1, i), where 1 ≤ i ≤ n.

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

출력 형식

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

예제 입력 1

6 3 1
0
3
3
2
9
0

예제 출력 1

4.00

예제 입력 2

6 3 2
0
3
3
2
9
0

예제 출력 2

6.00