Description

You downloaded a card game.

The rules of this game are as follows:

1. There are $n$ cards in total. Each card has a type. There are $n$ possible types, represented by integers $1 \sim n$. There is also a scoring parameter $k$.
2. You draw these $n$ cards in order. For each card, you have two choices: take it or discard it.
3. In all cases, you must ensure that the cards in your hand contain only one type.
4. After finishing drawing cards, you may choose to score your hand. The score is calculated as follows: if you have $x$ cards, you gain $x^{\frac{1}{2}k}$ points. After scoring, your hand will be cleared, and the points will be added to your total score.

Now, you want to compute the maximum possible total score in this card game.

Input Format

The first line contains two integers $k, n$.

The next $n$ lines each contain one integer, representing the type of a card.

Output Format

Output one real number in a single line, representing the maximum score that can be achieved.

3 5
1
2
2
1
1

6.656854249

4 5
1
2
2
1
1

9.0

Hint

Sample Explanation

Sample 1 Explanation

The best strategy is to discard no cards, and score after drawing the 1st, 3rd, and 5th cards. The score is $1^{1.5} + 2^{1.5} + 2^{1.5} \approx 6.656854249$.

Sample 2 Explanation

There are two optimal strategies. One is to discard the cards of type $2$, and score after drawing the 5th card, gaining $3^2 = 9$ points in total.

The other is the same as Sample 1, with score $1^{2} + 2^{2} + 2^{2} = 9$.

SPJ Scoring Standard

Let your answer be $p$ and the standard answer be $q$. If $\frac{|p-q|}{q} \le 10^{-6}$, you will be accepted.

Constraints and Limits

For $100\%$ of the testdata, it is guaranteed that $2 \le k \le 4$, $1 \le n \le 10^6$, and the card type $\in \{1,n\}$.

Notes

This problem is translated from Canadian Computing Olympiad 2019 Day 2 T1 Card Scoring.

Translated by ChatGPT 5