시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)220716433.862%

문제


 

고등학생 때였다. 친구의 손에 이끌려 처음으로 가게 된 화장품 가게는 문을 열자마자 은은한 향기가 코끝을 스치는 곳이었다. 친구를 따라가기에 급급했던 한별이의 발걸음은 이제 누가 말하지 않아도 무언가에 빨려 들어간 듯이 앞을 향했다. 파운데이션을 바르고, 블러셔를 두드리고. 거울을 본 한별이는 처음 보는 자신의 모습에 푹 빠져버렸다. 얼굴에 띈 홍조는 블러셔가 무색해질 정도였다. 그런 기분에 감화된 탓인지 화장품 가게를 나서서 집에 돌아갈 때까지도 거울의 그 모습을 잊을 수가 없었다. 마치 자기가 주목받는 느낌이 들어 볼이 한번 더 붉어져 왔다. 한별이는 이 기분을 다른 사람에게도 전해주고 싶어서 나중에 꼭 화장품 가게를 열겠다고 다짐했다.

그동안 이룬 결실도, 못다 한 각오도 있었다. 하지만 화장품 가게를 열겠다는 노력의 결과는 눈앞으로 다가와서, 내일은 한별이의 화장품 가게가 개점한 지 꼬박 1년 되는 날이 된다. 한별이의 화장품 가게는 만들어진 지 얼마 안 되었지만 많은 인기를 얻어 멀리서까지도 화장품을 사러 찾아온다. 이 화장품 가게의 인기 상품은 총 용량이 $X$㎖인 헤어에센스이고, 특유의 매력적인 딸기향은 모발의 상처만큼이나 마음의 상처를 치유하는 데에도 유용하다.

한별이의 화장품 가게에서는 불필요한 쓰레기를 줄이자는 재활용 캠페인을 하고 있다. 한별이의 가게의 모든 상품은 재활용이 가능한 용기에 담긴다. 가게로 사용하다 남은 헤어에센스 용기 두 개를 반납하면 새로운 용기에다가 남은 헤어에센스를 모아 주고, 추가로 총 용량의 절반만큼의 헤어에센스를 추가로 채워준다. 단, 총 용량을 넘쳐서 채워주지는 않는다. 다시 말해, 용량이 각각 $A$㎖와 $B$㎖ 남은 헤어에센스를 가져가면 $\min\left(A+B+\frac{X}{2},\ X\right)$㎖의 헤어에센스가 담긴 새로운 용기로 바꿔준다.

한별이의 화장품 가게 단골인 히나는 이제까지 사모은 헤어에센스 용기가 $N$ 개 있다. $i$ 번째 용기에는 헤어에센스가 $C_i$㎖ 담겨 있다. 히나는 한별이의 화장품 가게에 적당한 순서로 헤어에센스를 교환해서 용량이 꽉 찬, 즉, $X$㎖가 담겨 있는 헤어에센스 용기를 최대한 많이 만들고 싶다. 히나가 용량이 꽉 찬 헤어에센스를 최대 몇 개 만들 수 있는지 알려주자.

입력

다음과 같이 입력이 주어진다.

$N$ $X$

$C_1$ $C_2$ $\dots$ $C_N$

  • $N$은 히나가 가진 헤어에센스 용기의 수이다. ($1 \le N \le 100\,000$)
  • $X$는 헤어에센스 용기의 총 용량이다. ($1 \le X \le 10^{18}$)
  • $C_i$는 $i$ 번째 용기에 담겨 있는 헤어에센스의 용량이 $C_i$㎖라는 의미이다. ($0 \le C_i \le X$)
  • 입력으로 주어지는 모든 수는 정수다.

출력

한별이의 화장품 가게에 가서 적당한 순서로 헤어에센스를 교환해서 용량이 꽉 찬 헤어에센스 용기를 몇 개 만들 수 있는지 출력하여라.

예제 입력 1

7 13
0 1 2 3 5 8 13

예제 출력 1

3

첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용기를, 다섯 번째 용기와 여섯 번째 용기를 가져가서 용량이 $13$㎖남은 헤어 에센스 용기를 받을 수 있다. 마지막으로 용량이 $7.5$㎖ 남은 용기와 $11.5$㎖ 남은 용기를 가져가서 용량이 $13$㎖ 남은 헤어 에센스 용기를 하나 더 받을 수 있다.