Description

Little A goes to the Olympics.

There are $n$ judges in total, who give Little A scores $a_1,a_2,\ldots,a_n$.

Little A is not satisfied with his scores, so he increases the score given by one judge by $1$. This is called one operation.

However, Little A cannot be too greedy: he can perform at most $m$ operations.

Little A's final score is the average of all scores after removing one highest score and one lowest score.

Little A wants to know the maximum possible final score.

Input Format

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

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$.

Output Format

For easier output, Little A only needs to know what final score $\times (n-2)$ is.

3 2
1 2 3

3

4 3
1 2 2 3

6

Hint

[Sample 1 Explanation]

One feasible plan is: $[1,2,3]\to [3,2,3]$.

[Sample 2 Explanation]

One feasible plan is: $[1,2,2,3]\to [2,3,3,3]$.

[Constraints and Notes]

This problem uses bundled testdata.

• Subtask 1 (5 points): $m=0$.
• Subtask 2 (10 points): $n=3$.
• Subtask 3 (15 points): $n,m\le 10^3$.
• Subtask 4 (70 points): no special restrictions.

For $100\%$ of the testdata, $3\le n\le 10^5$, $0\le m,a_i\le 10^9$.

Translated by ChatGPT 5