AT_abc470_e [ABC470E] 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.

The input is given from Standard Input in the following format: > $ 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} $ .

### Sample Explanation 1 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.