안전한 포장

깨지기 쉬운 물건을 포장하는 포장 창고의 관리자가 피보나치 수열의 크기를 가진 상자들을 공급업체와 계약했다. 이유는 확실하지 않지만 최근 개봉한 영화 “다빈치 코드”와 관련이 있다는 소문이 돌고 있다. 수열에 있는 크기의 물건은 빈 공간 없이 같은 크기의 상자에 넣을 수 있지만, 수열에 없는 크기의 물건은 상자를 가득 채워 물건이 깨지지 않도록 충분한 완충재와 함께 포장해야 한다. 물건은 두 상자에 나누어 담을 수 없고, 각 물건은 반드시 자기 상자에 따로 담아야 한다. 같은 크기의 상자를 여러 개 사용하는 것은 허용된다.

이 이야기를 더 기이하게 만드는 두 번째 반전은 회사가 매일 크기 F의 완충재만 배송받는다는 점이다. 매일이 끝나면 남은 완충재는 모두 버려진다. 물건과 달리 완충재는 필요한 만큼 나눌 수 있다.

주어진 완충재의 크기 F와 물건 목록에 대해 매일 배송할 수 있는 물건 개수를 최대로 만드는 것이 여러분의 임무이다.

피보나치 수열 fib(n)은 다음과 같이 정의된다. $fib(n) = \begin{cases} n & \text{for } n < 2 \\ fib(n-1) + fib(n-2) & \text{for } n \ge 2 \end{cases}$

다음은 피보나치 수열의 처음 열한 개 수이다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .

처음 두 수를 제외한 각 수는 앞의 두 수를 더해서 얻어진다는 점에 유의하자.

이 문제의 입력은 하루 이상의 포장 작업으로 이루어진다. 각 날의 작업은 다음과 같이 두 줄로 주어진다.

• 첫째 줄에는 세 정수가 주어진다. 포장할 물건의 수 W (0 < W < 1000), 사용 가능한 완충재의 크기 F (1 < F < 1000), 물건 크기의 최댓값 S (1 < S < 108). 정수는 공백으로 구분된다.
• 다음 줄에는 포장할 물건의 크기를 나타내는 W개의 정수가 공백으로 구분되어 주어진다.

입력은 공백으로 구분된 세 개의 0으로 이루어진 줄로 끝난다. 이 줄은 처리하지 않는다.

각 날에 대해 그날 포장할 수 있는 물건의 개수를 한 줄에 출력한다.