题目描述

有 $n$ 张卡牌，每张卡牌有权值 $a_{i}$，薇老师和静老师轮流抽卡，薇老师先手。

在每一回合中，玩家可以依次进行以下动作：

• 从卡堆随机选取至多 $m$ 张卡。
• 选择其中一张卡牌给薇老师，或者可以选择不给。
• 将其余卡牌放回。

此时若卡堆中只剩下 $K$ 张牌，则游戏结束。

薇老师希望自己最终获得的卡牌权值和尽可能大，而静老师希望薇老师的尽可能小，求薇老师最终获得的权值和的期望。

输入格式

第一行三个整数 $n,m,K$。意义如题所述。

第二行 $n$ 个整数 $a_i$，表示 $n$ 张卡牌各自的权值。

输出格式

一行一个实数，表示答案。绝对误差不超过 $10^{-5}$。

数据范围

对于所有数据，保证：$1 \le m,K \le n \le15,1\le a_i \le1000$。

输入样例 1

2 2 1
1 2

输出样例 1

2.000000

输入样例 2

3 2 1
1 2 3

输出样例 2

4.000000

样例解释

对于样例 $1$ ：

薇老师的最优策略为：第一轮就取走第二张牌，随即游戏结束。期望为 $2$。

对于样例 $2$ ：

薇老师的最优策略为：绝不选前两张牌，这样必能得到第三张。 静老师的最优策略为：绝不选后两张牌，这样必能得到第一张。因此期望为 $1+3=4$。