26491번 - NiceSet 서브태스크다국어

The Great Kagura loves the number $S$. In front of her, she has a sequence of integers $a_1, \dots , a_n$. She wants to select a collection of these integers such that the sum of the absolute values of the differences of all pairs of integers in her collection is at most $S$. For example, if her collection is $x$, $y$, $z$, then $|x − y| + |x − z| + |y − z| ≤ S$. She wants to select the largest collection that she can. Can you help her?

The first line of the input contains the two integers $n$ and $S$. The second line of the input contains $a_1, \dots , a_n$.

Output the size of the largest collection of integers from among $a_1, \dots , a_n$ that satisfy the required condition.

• $1 ≤ n ≤ 300\,000$
• $1 ≤ a_i ≤ 1\,000\,000\,000$
• $1 ≤ S ≤ 10^{18}$