Informatica Online Judge

  책장 [0217 / 00D9]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 128   Total Tried : 399


The Champion of this Problem (C++) : gs18105 - ms / 295byte
My Best Submission (C++) : N/A

[]

Background

농부 존은 최근 소 도서관을 만들기 위해서 새로운 책장을 구입하였다. 하지만 이 책장은 금새 책들로 가득차게 되었다.

지금 이 책장에 남은 공간은 맨 위쪽 단 밖에 남지 않은 상태이다.

이 도서관에는 키가 Hi ( 1 <= Hi <= 10,000 )인 소들이 N마리( 1 <= N<= 20,000 )가 있다. 그리고 그 N마리의 모든 소들의 키의 합을 S라고 하면, 책장의 높이 B는 1 <= B <= S <= 2,000,000,007이라는 조건이 성립한다.

맨 위쪽 단에 책을 넣기 위해서는 각 소들이 서로를 머리위로 쌓아 올려서 키를 크게 만들어서 넣어야 한다.

이 때 쌓아 올린 최종 키는 각 소들의 키의 합과 같다.

그리고 이 합한 키가 반드시 책장높이와 같거나 더 커야 맨 위쪽 단을 이용할 수 있다고 한다.

하지만 너무 많은 소가 서로 머리위로 올라가게 되면 위험 부담이 커지므로 최소한의 소를 서로 올려서 최고 윗단을 이용하고 싶어한다.

맨 위쪽단을 이용하기 위해 이용될 가장 적은 소의 마릿수를 구하는 프로그램을 작성하시오.

Input

첫째 줄에는 2개의 공백으로 구분된 정수 N, B가 차례로 입력된다. 다음 줄부터 N+1번째 줄까지 각 소들의 키가 한 줄에 하나씩 주어진다.

Output

맨 위쪽 책장을 이용하기 위해서 일할 최소의 소의 수를 출력한다.

IO Example

입력
6 40
6
18
11
13
19
11

출력
3


출처 : USACO (http://ace.delos.com)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]