똑같은 목도리

면접 대비

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

요약

n개의 목도리 길이와 k개의 순간이 주어지고 한 순간에 한 줄을 뜨거나 풀 수 있을 때, k번 안에 같은 길이로 맞출 수 있는 목도리 개수의 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 정렬, 그리디, 이분 탐색, 누적 합
정답자: 아직 제출이 없습니다

문제

Maggy는 목도리를 떠서 용돈을 번다. 오늘은 운이 좋게도 상인이 목도리를 최대한 많이 사겠다고 제안했는데, 조건이 하나 있다. 상인은 길이(단의 수)가 모두 같은 목도리만 원한다. 그렇지 않으면 가게에 진열했을 때 보기 안 좋기 때문이다. 상인은 정확히 $k$ 순간 뒤에 돌아오겠다고 말했다. Maggy는 모든 목도리의 현재 길이를 알고 있고, 한 단을 뜨거나 푸는 데 한 순간이 걸린다. Maggy가 길이가 같은 목도리를 최대 몇 개까지 만들 수 있는지 구하자.

입력

첫째 줄에 정수 $n$ 과 $k$ 가 공백 하나를 사이에 두고 주어진다( $1 \leq n \leq 10^5$ , $0 \leq k \leq 10^9$ ). 각각 목도리의 개수와 상인이 돌아오기까지 남은 순간의 수다. 둘째 줄이자 마지막 줄에 $n$ 개의 자연수 $a_i$ 가 공백 하나를 사이에 두고 주어진다( $1 \leq a_i \leq 10^9$ ). 각 목도리의 길이를 단의 수로 나타낸 값이다.

출력

첫째 줄이자 유일한 줄에 정수 하나를 출력한다. Maggy가 상인이 돌아오기 전까지 만들 수 있는, 길이가 같은 목도리의 최대 개수다.

힌트

$6$ 순간이면 Maggy는 모든 목도리의 길이를 $2$ 로 같게 만들 수 있다.

예제1

예제 1
입력
```
5 6
1 2 3 4 4
```
예상 출력
```
5
```