Description

To make the members of our team more united, we want everyone’s skill level to be as balanced as possible. At this time, someone needs to make some changes to themselves.

Our team has $n$ students. The skill value of the $i$-th student is an integer $a_i$.

We consider the team to be united when the variance of the whole group’s skill values is no more than $m$.

What is the minimum number of students who must change their skill values (they may change them to any real number) so that the team can become united?

To avoid precision errors when reading input, the given $m$ is $n$ times the real value, and this value is an integer.

---

If you do not know what variance is, here is the basic concept:

Variance is an indicator that measures how much a set of data fluctuates.

Let the average of a sequence $a_{1\dots n}$ of length $n$ be $p$. Then the variance $S$ of this sequence is:

$$S=\frac{1}{n} \sum_{i=1}^n(a_i-p)^2$$

Input Format

The first line contains integers $n,m$, representing the number of students and $n$ times the upper limit of the variance.

The second line contains $n$ integers $a_{1\cdots n}$, representing each student’s skill value.

Output Format

The first line contains an integer $t$, representing the minimum number of people whose skill values must be changed.

4 32
3 7 -5 -1

1

5 18
1 4 3 6 9

1

6 679
5 83 56 20 54 111

3

Hint

[Sample 1 Explanation]

In this sample, $n=4$, and the real $m=\dfrac{32}{n}=8$.

At the beginning, the average of all students’ skill values $a_i$ is $1$, and the variance is:

$$S=\dfrac{1}{4}[(3-1)^2+(7-1)^2+(-5-1)^2+(-1-1)^2]=20$$

After changing the 3rd student’s skill value to $3$, the average becomes $3$, and the variance is:

$$S=\dfrac{1}{4}[(3-3)^2+(7-3)^2+(3-3)^2+(-1-3)^2]=8$$

Only $1$ person’s skill value was changed, which meets the requirement.

[Sample 2 Explanation]

In this sample, $n=5$, and the real $m=\dfrac{18}{n}=3.6$.

At the beginning, the average of all students’ skill values $a_i$ is $4.6$, and the variance is $7.44$:

After changing the 5th student’s skill value to $3.5$, the average becomes $3.5$, and the variance is $2.6$.

Only $1$ person’s skill value was changed, which meets the requirement.

---

[Constraints]

Subtask ID	$n\leq$	Points
1	$16$	15
2	$300$	17
3	$10^3$	20
4	$5\times 10^3$	7
5	$10^4$	8
6	$2\times 10^5$	33

For all test points, $1\leq n\leq 2\times 10^5$, $1\leq m\leq 10^{18}$, and $0\leq |a_i|\leq 10^6$.

Translated by ChatGPT 5