AT_abc470_e.Concentration

Takahashi is playing a solitaire game similar to the memory-matching game.

There are $2N$ cards. A number is written on the front of each card, and nothing is written on the back.
For each $i$ satisfying $1 \leq i \leq N$, there are exactly two cards on which $A_i$ is written. (The $A_i$ are pairwise distinct.)

Takahashi plays the game with these cards using the following procedure.

• Shuffle the $2N$ cards and lay them out face down.
• Set life to $L$ and score to $0$.
• Repeat the following until life becomes $0$ or there are no cards left on the table:
  • Choose one face-down card on the table, turn it face up, and check the number $X$ written on it.
  • Choose one face-down card on the table, turn it face up, and check the number $Y$ written on it.
  • If $X=Y$, remove those two cards from the table, and increase the score by $X$.
  • If $X\neq Y$, turn the two cards face down again, and decrease life by $1$.

Find the expected value of the score at the end of the game when Takahashi acts optimally to maximize the score at the end of the game.

Below is a more formal description of the game.

• Takahashi knows the rules of this game described below.
• Takahashi knows the values of $A_1,\dots,A_N$.
• Let $B$ be a sequence obtained by choosing a permutation of the length-$2N$ sequence $(A_1,A_1,A_2,A_2,\ldots,A_N,A_N)$ uniformly at random.
• Initially, Takahashi knows none of the values of $B$. Once he learns the value of $B_i$, he remembers it completely thereafter.
• Let life be $L$, score be $0$, and $S$ be ${1,2,3,\ldots,2N}$. Takahashi always knows these values.
• Repeat the following until life becomes $0$ or $S$ becomes empty:
  • Based on the information obtained up to this point, Takahashi chooses an element from $S$, and calls it $i$.
  • The value of $B_i$ is revealed, and Takahashi learns it.
  • Based on the information obtained up to this point (including the value of $B_i$), Takahashi chooses an element from $S\setminus{i}$, and calls it $j$.
  • The value of $B_j$ is revealed, and Takahashi learns it.
  • If $B_i=B_j$, remove $i$ and $j$ from $S$, and add $B_i$ to the score.
  • If $B_i \neq B_j$, decrease life by $1$.
• Takahashi acts optimally to maximize the expected value of the score at the end of the game.

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

共有 $2N$ 张卡片。每张卡片正面写有一个数字，背面为空白。
对每个满足 $1 \leq i \leq N$ 的 $i$，恰好有两张卡片上写着 $A_i$。（这些 $A_i$ 两两互异。）

高桥使用如下规则用这些卡片进行游戏：

• 将 $2N$ 张卡片随机洗牌，并全部背面朝上摊开。
• 将 生命值（life） 设为 $L$，得分（score） 设为 $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$。
• 高桥采取最优策略，以最大化游戏结束时得分的期望值。

The input is given from Standard Input in the following format:

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

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

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

Output the answer.
Your output will be considered correct if its absolute or relative error from the true answer is at most $10^{-5}$.

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

Sample 1 Explanation:
The game may proceed as follows, for example. To distinguish the six cards, let us call them A, B, C, D, E, F.

• Start the game with life $2$ and score $0$.
• Turn card A face up. $3$ is written on it.
• Turn card B face up. $2$ is written on it.
• Since different numbers are written, turn both cards face down again, and decrease life by $1$ to $1$.
• Turn card C face up. $3$ is written on it.
• Turn card A face up. $3$ is written on it.
• Since the same number is written, remove both cards from the table, and increase the score by $3$ to $3$.
• Turn card D face up. $1$ is written on it.
• Turn card E face up. $2$ is written on it.
• Since different numbers are written, turn both cards face down again, and decrease life by $1$ to $0$.
• Since life has become $0$, the game ends. The score is $3$.

Note that, immediately after turning card C face up in this sequence, Takahashi can make the choice of "turning face up card A, the other already-known card with $3$ written on it, based on the fact that $3$ was written on the front of card C."

Constraints

• $1 \leq N \leq 200$
• $1 \leq L \leq 200$
• $1 \leq A_1 < A_2 < \dots < A_N \leq 10^5$
• All input values are integers.

样例 1 解释：
游戏可能按如下方式进行（例如）。为区分六张卡片，我们将其分别记为 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$。

注意：在此序列中，当 Takahashi 刚翻开卡片 C 后，他可立即根据“卡片 C 正面写有数字 $3$”这一信息，选择翻开另一张已知正面写有 $3$ 的卡片（即卡片 A）。

限制条件

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