Card Scoring

Έχετε μια τράπουλα με ~n~ κάρτες. Κάθε κάρτα έχει μια τιμή: οι τιμές των καρτών βρίσκονται μεταξύ του ~1~ και του ~n~, πιθανώς με κάποιες επαναλαμβανόμενες τιμές, και πιθανώς με κάποιες τιμές που δεν εμφανίζονται ποτέ. Υπάρχει επίσης ένας ειδικός ακέραιος ~k~ που θα χρησιμοποιηθεί για τον υπολογισμό μιας βαθμολογίας.

Παίζετε ένα παιχνίδι που περιλαμβάνει το τράβηγμα όλων των καρτών από την τράπουλα μία προς μία. Οταν τραβήξετε μια κάρτα, μπορείτε να επιλέξετε είτε να την προσθέσετε στο χέρι σας είτε να την ξεσκαρτάρετε. Μπορείτε επίσης να σκοράρετε ολόκληρο το χέρι σας ανά πάσα στιγμή. Όταν σκοράρετε ένα χέρι με ~x~ κάρτες, κερδίζετε ~x^{(1/2) k}~ πόντους και μετά πετάτε όλες τις κάρτες από αυτό το χέρι. Σε οποιαδήποτε χρονική στιγμή, το χέρι σας μπορεί να περιέχει μόνο κάρτες με τon ίδιo αριθμό πάνω τους. Δεδομένης της αρχικής σειράς των καρτών στην τράπουλα, ποια είναι η μέγιστη δυνατή βαθμολογία που μπορείτε να πάρετε;

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει δύο, χωρισμένους με κενό, ακέραιους ~k~ και ~n~. Η τιμή ~k~ είναι η τιμή που χρησιμοποιείται στην πράξη ~x^{(1/2) k}~ για τον υπολογισμό των πόντων (~2~ ~\le~ ~k~ ~\le~ ~4~). Η τιμή ~n~ είναι ο αριθμός των καρτών στην τράπουλα (~1~ ~\le~ ~n~ ~\le~ ~1\,000\,000~), Οι επόμενες ~n~ γραμμές περιέχουν έναν ακέραιο ανα γραμμή, όπου η ~i~-οστη από αυτές τις ~n~ γραμμές είναι η ~i~-οστη κάρτα από την κορυφή της τράπουλας (~1~ ~\le~ ~i~ ~\le~ ~n~).

Βαθμολογία

Για ~4~ από τους ~25~ διαθέσιμους βαθμούς, ~1~ ~\le~ ~n~ ~\le~ ~20~.

Για επιπλέον ~1~ από τους ~25~ διαθέσιμους βαθμούς, ~1~ ~\le~ ~n~ ~\le~ ~300~, ~k~ = ~2~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~1~ ~\le~ ~n~ ~\le~ ~300~.

Για επιπλέον ~3~ από τους ~25~ διαθέσιμους βαθμούς, ~1~ ~\le~ ~n~ ~\le~ ~5\,000~.

Για επιπλέον ~3~ από τους ~25~ διαθέσιμους βαθμούς, ~k~ = ~4~.

Έξοδος

Εκτυπώστε έναν πραγματικό αριθμό (floating point number), ο οποίος είναι τη μέγιστη βαθμολογία που μπορείτε να λάβετε παίζοντας με τον βέλτιστο τροπο.

Αν η απάντησή σας είναι ~p~ και η σωστή απάντηση είναι ~q~, τότε η απάντησή σας θα θεωρηθεί σωστή αν

|~p~ - ~q~| / ~q~ ~\le~ ~10^{-6}~

Παραδείγματα

input

3 5
1
2
2
1
1

output

6.656854249

Επεξήγηση του 1ου παραδείγματος

Γνωρίζουμε ότι οι κάρτες που τραβάμε με τη σειρά είναι [~1~, ~2~, ~2~, ~1~, ~1~] και ότι αν σκοράρουμε ένα χέρι με ~x~ κάρτες μας δίνει ένα σκορ ~x^{1.5}~.

Η βέλτιστη στρατηγική είναι να τραβήξουμε μία κάρτα, να σκοράρουμε το χέρι μας, να τραβήξουμε δύο κάρτες, να σκοράρουμε το χέρι μας, και να τραβήξουμε άλλες δύο κάρτες και να σκοράρουμε το χέρι μας. Αυτή η στρατηγική μας δίνει ένα σκορ ~1^{1.5}~ + ~2^{1.5}~ + ~2^{1.5}~ ~\approx~ 6.656854249.

input

4 5
1
2
2
1
1

output

9.0

Επεξήγηση του 2ου παραδείγματος

Γνωρίζουμε ότι οι κάρτες που τραβάμε με τη σειρά είναι [~1~, ~2~, ~2~, ~1~, ~1~] και ότι αν σκοράρουμε ένα χέρι με ~x~ κάρτες μας δίνει ένα σκορ ~x^2~.

Μία βέλτιστη στρατηγική είναι να πάρουμε όλες τις κάρτες με τον αριθμό ~1~ και να τις σκοράρουμε όλες στο τέλος. Αυτή η στρατηγική δίνει σκορ ~3^2~ = ~9~. Σημειώστε ότι το να τραβήξουμε μία κάρτα, να σκοράρουμε το χέρι μας, να τραβήξουμε τις δύο επόμενες κάρτες, να σκοράρουμε το χέρι μας, και να τραβήξουμε τις τελευταίες δύο κάρτες και να σκοράρουμε το χέρι μας θα μας δώσει ένα σκορ ~1^2~ + ~2^2~ + ~2^2~ = ~9~.