Background

"The Wandering Moon" was released in Gensokyo.

Just as a thousand people have a thousand Hamlets in their hearts, the debate about it has also been quietly spreading.

At some point, a platform called "Huaban" appeared. It slowly replaced the street-side discussions and became the main battlefield of the controversy—because it has a rating feature. On the platform, rating posts that cite many sources and express different opinions became part of the daily life of Gensokyo’s residents, and everything seemed peaceful.

Until the Balancer appeared.

At first, nobody paid attention to this bit of noise. It was just a careless rebellion, a helpless emotion, a boring outburst. But as the idea of balance sank into people’s minds, the wave of egoism reached its peak, and the order of the rating system was almost collapsing.

Cirno felt she should do something.

Problem Description

Cirno decides to convince and save those who are swept up by egoism through calculation.

There are $n$ residents participating in the rating, and the platform’s maximum score is limited to $m$.

Before rating, each resident has a psychological expected score $a_i(a_i\in[0,m]\cap\mathbb{Z})$.

However, people will not rate directly according to their expected score. Instead, if the current average score on the platform is strictly higher than their expected score, they will say, "The score is too high, I’ll give a $0$ to balance it." Otherwise, they will say, "The score is too low, I’ll give a full score ($m$ points) to balance it."

Initially, the platform’s average score is $0$.

To show how destructive this rating method is to fairness, Cirno wants you to compute, over different permutations of these $n$ residents rating in different orders, the maximum and minimum possible final average score on the platform.

Input Format

The first line contains two integers separated by spaces, denoting $n$ and $m$.

The second line contains $n$ integers separated by spaces, denoting $\{a_n\}$.

Output Format

Output one line with two real numbers, each rounded to two decimal places, representing the maximum and minimum final average scores.

5 5
1 2 3 4 5

4.00 2.00

7 114
23 75 35 17 101 55 73

81.43 32.57

Hint

Constraints and Notes

For $100\%$ of the testdata, it is guaranteed that $1 < n,m\le 10^5$, and $a_i \in [0,m]$.

Subtasks

Subtask1 (10 points): $n \le 8$.

Subtask2 (10 points): $n \le 20$.

Subtask3 (30 points): $n \le 10^3$.

Subtask4 (50 points): No special constraints.

Translated by ChatGPT 5