你有一副包含 $n$ 张牌的牌堆。每张牌都有一个数值：牌的数值在 $1$ 到 $n$ 之间，可能存在重复的数值，也可能有些数值从未出现。此外，还有一个用于计算分数的特殊整数 $k$。

你正在进行一个游戏，需要将牌堆中的所有牌一张一张地抽出来。当你抽出一张牌时，你可以选择将其加入手牌或弃掉。你也可以在任何时候对手牌进行结算。当你结算一副包含 $x$ 张牌的手牌时，你会获得 $x^{\frac{1}{2}k}$ 分，然后弃掉这副手牌中的所有牌。在任何时刻，你的手牌中只能包含数值相同的牌。给定牌堆中牌的初始顺序，你能获得的最高分数是多少？

输入格式

输入的第一行包含两个空格分隔的整数 $k$ 和 $n$。$k$ 是用于计算分数的表达式 $x^{\frac{1}{2}k}$ 中的参数 ($2 \le k \le 4$)。$n$ 是牌堆中牌的数量 ($1 \le n \le 1\,000\,000$)。接下来的 $n$ 行每行包含一个整数，其中第 $i$ 行表示从牌堆顶部数起的第 $i$ 张牌 ($1 \le i \le n$)。

在总共 25 分的测试点中： 4 分满足 $1 \le n \le 20$。 另 1 分满足 $1 \le n \le 300, k = 2$。 另 5 分满足 $1 \le n \le 300$。 另 3 分满足 $1 \le n \le 5\,000$。 * 另 3 分满足 $k = 4$。

输出格式

输出一个浮点数，表示以最优策略进行游戏所能获得的最高分数。

如果你的答案是 $p$，标准答案是 $q$，那么当满足 $\frac{|p - q|}{q} \le 10^{-6}$ 时，你的答案将被视为正确。

样例

样例输入 1

3 5
1
2
2
1
1

样例输出 1

6.656854249

说明 1

我们知道抽出的牌顺序为 $[1, 2, 2, 1, 1]$，且结算一副包含 $x$ 张牌的手牌会获得 $x^{1.5}$ 分。 最优策略是：抽一张牌并结算，再抽两张牌并结算，最后再抽两张牌并结算。该策略获得的分数为 $1^{1.5} + 2^{1.5} + 2^{1.5} \approx 6.656854249$。

样例输入 2

4 5
1
2
2
1
1

样例输出 2

9.0

说明 2

我们知道抽出的牌顺序为 $[1, 2, 2, 1, 1]$，且结算一副包含 $x$ 张牌的手牌会获得 $x^2$ 分。 一种最优策略是：拿走所有数值为 $1$ 的牌，并在最后统一结算。该策略获得的分数为 $3^2 = 9$。注意，先拿第一张牌并结算，再拿接下来的两张牌并结算，最后拿剩下的两张牌并结算，同样可以得到 $1^2 + 2^2 + 2^2 = 9$。