NiceSet

시간 제한1초메모리 제한1024 MB

요약

주어진 수들에서 모든 쌍의 절댓값 차의 합이 S 이하가 되는 가장 큰 부분집합을 고른다.

난이도: 보통10점 중 6점
유형: 정렬, 슬라이딩 윈도우, 누적 합, 그리디
정답자: 아직 제출이 없습니다

문제

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}$

예제4

예제 1
입력
```
5 3
1 2 3 4 5
```
예상 출력
```
2
```
예제 2
입력
```
5 4
1 2 3 4 5
```
예상 출력
```
3
```
예제 3
입력
```
5 1
1 1 1 1 1
```
예상 출력
```
5
```
예제 4
입력
```
10 7
1 5 3 2 4 3 1 3 2 100
```
예상 출력
```
5
```