题目描述

高桥君正在玩一个类似记忆配对的单人纸牌游戏。

共有 $2N$ 张卡片。每张卡片的正面写有一个整数，背面什么都没有写。
对于每个满足 $1 \leq i \leq N$ 的 $i$，恰好有两张卡片上写着 $A_i$。（$A_i$ 两两不同。）

高桥君按照以下流程用这些卡片进行游戏。

• 将 $2N$ 张卡片洗混，背面朝上摆在桌面上。
• 将生命值设为 $L$，得分设为 $0$。
• 重复以下操作，直到生命值变为 $0$ 或桌面上没有卡片为止：
  • 选择桌面上一张背面朝上的卡片，将其翻至正面朝上，查看上面写的数字 $X$。
  • 再选择桌面上一张背面朝上的卡片，将其翻至正面朝上，查看上面写的数字 $Y$。
  • 若 $X=Y$，将这两张卡片从桌面上移除，得分增加 $X$。
  • 若 $X\neq Y$，将这两张卡片重新翻回背面朝上，生命值减少 $1$。

当高桥君采取最优策略以使游戏结束时的得分最大化时，求游戏结束时得分的期望值。

下面是该游戏更形式化的描述。

• 高桥君知道下文所述的游戏规则。
• 高桥君知道 $A_1,\dots,A_N$ 的值。
• 设 $B$ 是从长度为 $2N$ 的序列 $(A_1,A_1,A_2,A_2,\ldots,A_N,A_N)$ 的所有排列中均匀随机选取得到的一个序列。
• 初始时，高桥君不知道 $B$ 的任何一项的值。一旦他得知某个 $B_i$ 的值，此后他会完全记住它。
• 设生命值为 $L$，得分为 $0$，$S$ 为 $\{1,2,3,\ldots,2N\}$。高桥君始终知道这些值。
• 重复以下操作，直到生命值变为 $0$ 或 $S$ 变为空集：
  • 根据目前已获得的信息，高桥君从 $S$ 中选取一个元素，记为 $i$。
  • $B_i$ 的值被揭示，高桥君得知该值。
  • 根据目前已获得的信息（包括 $B_i$ 的值），高桥君从 $S\setminus\{i\}$ 中选取一个元素，记为 $j$。
  • $B_j$ 的值被揭示，高桥君得知该值。
  • 若 $B_i=B_j$，将 $i$ 和 $j$ 从 $S$ 中移除，得分增加 $B_i$。
  • 若 $B_i \neq B_j$，生命值减少 $1$。
• 高桥君采取最优策略，使游戏结束时得分的期望值最大化。

约束

• $1 \leq N \leq 200$
• $1 \leq L \leq 200$
• $1 \leq A_1 < A_2 < \dots < A_N \leq 10^5$
• 所有输入值均为整数。

输入

输入以以下格式从标准输入给出：

• $N$ $L$
• $A_1$ $A_2$ $\dots$ $A_N$

输出

输出答案。
若你的输出与真实答案的绝对误差或相对误差不超过 $10^{-5}$，则视为正确。

3 2
1 2 3

3.8666666667

例如，游戏可能按如下方式进行。为区分这六张卡片，称它们为 A、B、C、D、E、F。

• 以生命值 $2$、得分 $0$ 开始游戏。
• 翻开卡片 A，上面写着 $3$。
• 翻开卡片 B，上面写着 $2$。
• 由于数字不同，将两张卡片重新翻回背面朝上，生命值减少 $1$ 变为 $1$。
• 翻开卡片 C，上面写着 $3$。
• 翻开卡片 A，上面写着 $3$。
• 由于数字相同，将两张卡片从桌面上移除，得分增加 $3$ 变为 $3$。
• 翻开卡片 D，上面写着 $1$。
• 翻开卡片 E，上面写着 $2$。
• 由于数字不同，将两张卡片重新翻回背面朝上，生命值减少 $1$ 变为 $0$。
• 由于生命值变为 $0$，游戏结束。得分为 $3$。

注意，在上述流程中刚翻开卡片 C 之后，高桥君可以基于“卡片 C 正面写着 $3$”这一事实，做出“翻开卡片 A，即另一张已知的写着 $3$ 的卡片”这一选择。

5 2
2 3 5 7 101

17.8560846561

20 10
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200

770.7122293087

• 来源：AtCoder ABC 470 E

子任务设置

• 子任务 1（135 分）：$N,L \le 50$。
• 子任务 2（135 分）：$N,L \le 100$。
• 子任务 3（180 分）：无特殊限制。