Problem Background

This problem was used for the competition data.

However, yummy later felt it was unnecessary to strengthen it.

There exists a solution that does not use long double and __int128.

Problem Description

To make our team members more united, we need to ensure that the levels of all members are as balanced as possible. This requires some members to make changes to themselves.

Our team has $n$ members, and the level value of the $i$-th member is an integer $a_i$.

We consider the team to be united when the variance of the level values does not exceed $m$.

How many members, at least, need to change their level values (which can be changed to any real number), for the team to become united?

To avoid precision errors during input, the $m$ provided in the input is $n$ times the actual value, and this value is an integer.

If you are unfamiliar with variance, here is a basic concept of variance:

Variance is a measure of the fluctuation of a set of data.

Given a sequence $a_{1\dots n}$ of length $n$ with an average value $p$, the variance $S$ of the sequence is:

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

Input Format

The first line contains two integers $n$ and $m$, representing the number of members and $n$ times the variance limit, respectively.

The second line contains $n$ integers $a_{1\cdots n}$, representing the level values of each member.

Output Format

The first line contains an integer $t$, representing the minimum number of members whose level values need to be changed.

Sample Input and Output

Sample Input #1

4 32
3 7 -5 -1

Sample Output #1

1

Sample Input #2

5 18
1 4 3 6 9

Sample Output #2

1

Sample Input #3

6 679
5 83 56 20 54 111

Sample Output #3

3

Notes

Sample 1 Explanation

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

Initially, the average level value of all members 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 level value of the 3rd member 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 the level value of $1$ member was changed, meeting the requirements of the problem.

Sample 2 Explanation

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

Initially, the average level value of all members is $4.6$, and the variance is $7.44$:

After changing the level value of the 5th member to $3.5$, the average becomes $3.5$, and the variance is $2.6$.

Only the level value of $1$ member was changed, meeting the requirements of the problem.

Data Range

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

见题面 Input 部分

见题面 Output 部分