책장

면접 대비

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

요약

소들의 키와 책장 높이 B가 주어질 때, 키의 합이 B 이상이 되는 가장 적은 수의 소를 구한다.

난이도: 쉬움10점 중 3점
유형: 그리디, 정렬, 배열, 구현
정답자: 아직 제출이 없습니다

문제

농부 John이 소 도서관에 놓을 책장을 새로 샀습니다. 하지만 책장이 금방 가득 차서, 이제 비어 있는 공간은 맨 위쪽뿐입니다.

소는 모두 $N$ 마리( $1 \le N \le 20000$ )이며, 각 소 $i$ 의 키는 $H_i$ ( $1 \le H_i \le 10000$ )입니다. 모든 소의 키를 더한 값을 $S$ 라고 합니다. 책장의 높이는 $B$ ( $1 \le B \le S < 2000000007$ )입니다.

가장 키가 큰 소보다도 높은 책장 꼭대기에 닿으려면, 소 여러 마리를 위로 쌓을 수 있습니다. 이때 쌓은 소들의 전체 높이는 각 소의 키의 합이며, 이 합이 책장의 높이 $B$ 이상이 되어야 합니다. 필요 이상으로 많은 소를 쌓으면 위험하므로, 책장에 닿을 수 있으면서 쌓는 소의 수가 가장 적은 경우의 그 소의 수를 구하세요.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $B$
둘째 줄부터 $N+1$ 째 줄까지: $i+1$ 째 줄에는 정수 $H_i$ 하나가 주어집니다.

출력

첫째 줄: 책장에 닿을 수 있는 소들의 집합 중 크기가 가장 작은 것의 크기를 나타내는 정수 하나.

힌트

예를 들어 책장의 높이가 $40$ 일 때, $18+11+13$ 처럼 소 $3$ 마리로 도달하는 방법이 있으며, 그 밖에도 여러 방법이 있습니다.

예제1

예제 1
입력
```
6 40
6
18
11
13
19
11
```
예상 출력
```
3
```