题目描述

译自 CCO 2019 Day2 T1「Card Scoring」。

想象你有一叠牌，总共 $n$ 张。每张牌上都有一个数字，这些数字介于 $1$ 到 $n$ 之间，可能会有重复，也可能有些数字根本没有出现。另外还有一个特殊的数字 $k$，它会用来计算你的得分。

游戏规则是这样的，你要依次抽取这 $n$ 张牌。抽到一张牌的时候，你可以选择把它加入手牌或者丢弃。你还可以随时计算你手牌的总分。当你计算手牌分数时，如果有 $x$ 张相同的牌，你将获得 $x^{k/2}$ 分，然后丢掉手牌中的所有牌。也就是说，你手牌里的牌数字必须完全相同。现在告诉你卡牌的初始排列顺序，请问你能获得的最高分是多少呢？

输入格式

第一行包含两个用空格隔开的整数 $k$ 和 $n$。$k$ 是用来计算分数的表达式 $x^{k/2}$ 中的指数。$n$ 是卡牌的总数。接下来 $n$ 行，每行包含一个整数，代表卡牌从上到下的顺序。

输出格式

输出一个浮点数，代表你通过最佳策略所能获得的最高分。若你的输出的结果与正确答案的绝对误差或相对误差不超过 $10^{-6}$ 则视为正确。

3 5
1
2
2
1
1

6.656854249

已知抽到的卡牌顺序为 $[1,2,2,1,1]$，丢弃一组 $x$ 张相同的牌可以得到 $x^{1.5}$ 分。

最佳策略是：抽一张牌，计算得分；再抽两张相同的牌，计算得分；最后再抽两张相同的牌，计算得分。 这样可以得到 $1^{1.5}+2^{1.5}+2^{1.5} \approx 6.656854249$ 分。

4 5
1
2
2
1
1

9.0

已知抽到的卡牌顺序为 $[1,2,2,1,1]$，计算一组 $x$ 张相同的牌可以得到 $x^{2}$ 分。

最佳策略是：把所有数字为 $1$ 的牌都收集起来，最后一起计算得分。 这样可以得到 $3^{2}=9$ 分。 注意，也可以先抽一张 $1$，计算得分；然后抽两张 $2$，计算得分；最后抽两张 $1$，计算得分，这样也可以得到 $1^{2}+2^{2}+2^{2}=9$ 分。

数据范围与提示

对于 $16\%$ 的数据，$1 \leq n \leq 20$；
对于另外 $4\%$ 的数据，$1 \leq n \leq 300, k=2$；
对于另外 $20\%$ 的数据，$1 \leq n \leq 300$；
对于另外 $12\%$ 的数据，$1 \leq n \leq 5000$；
对于另外 $12\%$ 的数据，$k=4$；
对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$2 \leq k \leq 4$。