Adjusted Average

Time limit8sMemory limit1024 MB

Summary

Given n samples, remove at most k of them so the remaining average is as close as possible to a target value, and output the minimal absolute difference.

Level: Medium6 of 10
Topics: Sorting, Two pointers, Math
Solved: No attempts yet

Input

As a student of the Biology And Probability Course at your university, you have just performed an experiment as part of the practical assignments. However, your results do not look very nice: you had hoped that the average of your samples would be different from what it is now.

To improve your results, you decide to let some of your samples "magically disappear" (i.e., dump them in the waste bin). In order to not raise suspicion with your teacher, you can remove only a few of your samples. How close can you possibly get to your desired average?

Output

The input consists of:

One line with three integers $n$ , $k$ , and $\overline{x}$ ( $2 \leq n \leq 1500$ , $1 \leq k \leq 4$ , $k < n$ , $\left| \overline{x} \right| \leq 10^9$ ), the number of samples, the number of samples that may be removed, and the average you think looks the nicest.
One line with $n$ integers $x$ ( $\left| x \right| \leq 10^9$ ), representing the samples.

Output

Output the minimal absolute difference between $\overline{x}$ and the average you can obtain by removing at most $k$ samples from the dataset.

Your answer should have an absolute error of at most $10^{-4}$ .

Examples2

Example 1
Input
```
5 2 2
1 2 3 100 200
```
Expected output
```
0
```
Example 2
Input
```
5 4 -5
-6 -3 0 6 3
```
Expected output
```
0.5
```