题目描述

您下载了一款卡牌游戏。

这款游戏的规则如下：

1. 共有 $n$ 张牌，每张牌有一个种类，种类共有 $n$ 种，用 $1\sim n$ 的整数表示，同时还有一个评分参数 $k$。
2. 您按顺序摸这 $n$ 张牌，每张牌有两种选择，拿走或不要。
3. 在任何情况下，您都要保证，您的手上的牌里只能有一种种类的牌。
4. 在摸完牌后，您可以选择结算您的分数。分数的计算方式为：若您有 $x$ 张牌，您会获得 $x^{\frac{1}{2}k}$ 的分数。结算完分数后，您的手牌将被清空，且您的总分会进行累加。

现在，您决定计算，这款手牌游戏可能取得的总分的最大值是多少。

输入格式

第一行为两个整数 $k,n$。

接下来 $n$ 行，一行一个数，表示牌的种类。

输出格式

仅一行一个实数，表示可能取得的最高分。

3 5
1
2
2
1
1

6.656854249

4 5
1
2
2
1
1

9.0

提示

样例解释

样例 1 解释

最优方案为不放弃每一张牌，摸完第一、三、五张牌后计分，分数为：$1^{1.5}+2^{1.5}+2^{1.5}\approx 6.656854249$。

样例 2 解释

最优方案有两种，一种是弃掉种类为 $2$ 的牌，在第五张牌摸完后计分，共得 $3^2=9$ 分。

另一种同样例一，分数为：$1^{2}+2^{2}+2^{2}=9$。

SPJ 计分标准

设您的答案为 $p$，标准答案为 $q$，若 $\frac{|p-q|}{q}\le 10^{-6}$，您可以 AC。

数据范围及限制

对于 $100\%$ 的数据，保证 $2\le k\le 4$，$1\le n\le 10^6$，牌的种类 $\in \{1,n\}$。

说明

本题译自 Canadian Computing Olympiad 2019 Day 2 T1 Card Scoring。