## Problem
你參加了由 Google 舉辦的 KickStart 幸運抽抽樂活動，有許多豐富且高價 (以及一些低廉) 的獎品在等著你！

在這個抽抽樂活動中，有一個袋子內裝有 **N** 個獎品。每個獎品都有其對應的價值，準確地來說，對第 `i` 個獎品而言具有的價值為 $V_i$。玩家將手放入袋中後，將隨機取出一個獎品；每個獎品被抽中的機率皆相等。主辦方希望能給玩家一些選擇的機會，因此在玩家抽出獎品後，可以選擇保留獎品並結束抽取，抑或是將獎品放回袋中並重抽一次 (注意到此時再抽中剛放回的獎品的機率和抽中其他獎品的機率是一樣的)。玩家被規定最多只能重抽 **K** 次。即若已經抽了 **K** 次，那麼玩家必須保留第 **K** + 1 次抽取抽到的獎品並結束抽取。

倘若玩家在抽取過程中皆採用最佳策略以最大化其最終獲得的獎品的價值，請計算該玩家最終獲得的獎品價值之期望值。

## Input
第一行會輸入一個整數 **T**，表示接下來輸入測資的數量。緊接著會有 **T** 筆測資。

每個測資均包含兩行。第一行包含兩個整數：**N** 和 **K**，分別表示抽獎袋中獎品的數量以及單個玩家最多能夠重抽的次數。第二行包含了 **N** 個整數 $V_i$，分別表示第 `i` 個獎品的價值。

## Output
對每筆測資而言，均印出一行格式為 `Case #x: y` 的字串，其中 x 表示測資編號 (從 1 開始)，而 y 表示上述的期望值，且須為一個七位小數。舉例而言，倘若期望值為 `2.48`，則須印出 `2.4800000`；若期望值為 `1.666...`，則須印出 `1.6666667`。若你印出的答案和標準答案的絕對或相對誤差小於等於 $10^{-6}$ 即會被視為正確 (nt.1)。

## Limits
記憶體限制：1 GB
$1 \le$ **T** $\le 100$
$1 \le V_i \le 10^9$
$1 \le$ **N** $\le 2 \times 10^4$

### Small dataset (測資組 1)
時間限制：20 秒
$0 \le$ **K** $\le 1$

### Large dataset (測資組 2)
時間限制：60 秒
$0 \le$ **K** $\le 5 \times 10^4$

## Sample
Sample Input

5
4 0
1 2 3 4
3 1
1 10 1
3 15
80000 80000 80000
1 1
10
5 3
16 11 7 4 1

Sample Output

Case #1: 2.5000000
Case #2: 6.0000000
Case #3: 80000.0000000
Case #4: 10.0000000
Case #5: 12.3584000

在第一筆測資中，玩家不能重抽，因此期望值即為所有獎品價值之平均：$\frac{(1+2+3+4)}4=2.5$

在第二筆測資中，最好的策略為當抽到價值為 10 之獎品時保留，否則就重抽。抽中該獎品的機率 (包含第一次或第二次) 為 $1-(\frac23)^2=\frac59$，因此期望值即為 $\frac59\times10+\frac49\times1=6$。

在第三筆測資中，由於所有獎品之價值都一樣，因此不論玩家重抽幾次，其期望值均為 80000。

注意到第三筆和第五筆測資不會出現在測資組 1 內。

## Test Data
[Download Dataset](https://codejam.googleapis.com/dashboard/get_file/AQj_6U3q0h44E_U13JvN6hCvgtLBjMvbikRFmQWxdjxJBOGOydkVzXIFG6URAF-AnUUOzTtPd3hemQ/test_data.zip?dl=1)

## Solution
:::spoiler

#include <bits/stdc++.h>
using namespace std;

int binSearch(int n, const vector<double>& v, double spl) {
    if (n == 1) return v[0] > spl;
    int l = 0, h = n, m = (l + h) / 2;
    while (m < n && m > 0) {
        if (v[m] > spl) {
            if (v[m - 1] <= spl) return m;
            else h = m - 1;
        } else {
            l = m + 1;
        }
        m = (l + h) / 2;
    }
    return m;
}

double calEV(int n, const vector<double>& v, double lastEV) {
    int spl = binSearch(n, v, lastEV);
    double sum = lastEV * spl;
    for (int i = spl; i < n; ++i)
        sum += v[i];
    return sum / n;
}

double solve(int n, int k, vector<double>& v) {
    double mean = accumulate(v.begin(), v.end(), 0.0) / n;
    if (k == 0) return mean;
    sort(v.begin(), v.end());
    double ev[k + 1];
    ev[0] = mean;
    for (int i = 1; i <= k; ++i)
        ev[i] = calEV(n, v, ev[i - 1]);
    return ev[k];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed; cout.precision(7);
    int t; cin >> t;
    for (int i = 0; i < t; ++i) {
        int n, k; cin >> n >> k;
        vector<double> v;
        for (int j = 0; j < n; ++j) {
            int vj; cin >> vj;
            v.push_back(vj);
        }
        cout << "Case #" << i + 1 << ": " << solve(n, k, v) << '\n';
    }
}

:::

## Notes
nt.1: 即只要相對誤差或絕對誤差任一者小於 $10^{-6}$ 即可。舉例而言，若標準答案為 `1234567.8900000`，那麼容許的絕對誤差範圍為 $1234567.89\pm10^{-6}$，即 $[1234567.8899990,1234567.8900010]$；容許的相對誤差範圍為 $1234567.89\pm10^{-6}\times1234567.89$，即 $[1234566.65543211,1234569.12456789]$，又因答案須為七位小數，因此修正後的正確範圍應為 $[1234566.6554322,1234569.1245678]$。由於只要有任一範圍達到即可，因此最終的容許範圍應為兩誤差範圍的聯集，即後者；同上所述，若標準答案為 `0.1234567`，那麼修正過後的絕對誤差範圍為 $[0.1234557,0.1234577]$，相對誤差範圍為 $[0.1234566,0.1234568]$，取聯集即為前者。