This page is still under construction.

Parts of this page are still being built. What you see may change.

Safe Packing

Time limit2sMemory limit512 MB

Summary
Each day, choose boxes from the Fibonacci sizes so that every non-Fibonacci item's box is filled with the limited daily filling, packing as many items as possible.
Level

Medium6 of 10

Topics
Greedy, Sorting, Math, Brute force
Solved
No attempts yet

Problem

The manager of a packing warehouse that specialises in packing breakable items contracted a supplier for boxes whose sizes come from the Fibonacci sequence. I am not sure of the reason, but it is rumoured to be related to the recent "Da Vinci Code" movie. An item whose size is in the sequence can be packed in a box of the equal size without filling, but an item whose size is not in the sequence must be packed with enough filling material to fill the box and protect the item from breaking. An item cannot be split between two boxes, and each item must be packed separately in its own box. It is allowed to use multiple boxes of the same size.

The second twist in this story, which makes it more bizarre, is that the company only receives a daily delivery of filling material of size F. At the end of each day, any unused filling material is discarded. Unlike the items, the filling material can be split as needed.

Your task is to maximize the number of items shipped each day for a given size of filling material F and a given list of items.

The Fibonacci sequence fib(n) is defined as: fib(n)={nfor n<2fib(n−1)+fib(n−2)for n≥2fib(n) = \begin{cases} n & \text{for } n < 2 \\ fib(n-1) + fib(n-2) & \text{for } n \ge 2 \end{cases}

Here are the first eleven numbers of the Fibonacci sequence:

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

Note that each number, with the exception of the first two, is obtained by adding the preceding two numbers.

Input

The input to this problem consists of packing tasks for one or more days. The tasks for each day are described by two lines as follows:

  • The first line consists of three integers: the number of items to be packed, W (0 < W < 1000); the available size of filling material, F (1 < F < 1000); and the maximum size of items, S (1 < S < 108). The integers are separated by spaces.
  • The following line contains W integers separated by spaces that describe the sizes of items to be packed.

The input will be terminated by a line that consists of three zeros, separated by spaces. This line should not be processed.

Output

For each day, the output consists of one line that contains the number of items that can be packed for that day.

Examples1

  1. Example 1

    Input
    4 10 30
7 15 30 5
11 100 5812167
20 40 30 15 17 5812167 23 43 33 13 37
0 0 0
    Expected output
    3
10