Warehousing

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem types

Larry got a new job at a warehouse! His job is to package items into boxes, and move them into storage. Unlike most other warehouses, however, this warehouse is forward-thinking and promotes diversity. Because of this, Larry is tasked with maximizing diversity in the boxes he packages.

There are items on a conveyor belt in front of Larry of which he must package. Larry must take the items off the conveyor belt in the order they are on the conveyor belt, or else he will mess up the automatic system. Each item has a size and a type .

Since the warehouse promotes diversity, Larry must maximize the sum of the diversity of all the boxes that he packages. The diversity of a box is defined as the number of distinct types of items in the box.

However, there are some restrictions. Each box has a capacity of (the sum of the sizes of the items in the box must not exceed ). Since the warehouse is also Eco-Friendly, each box must have at least sum of item sizes, as to not waste cardboard.

Input Specification

The first line will contain three integers: , and .

The next line will contain integers .

The final line will contain integers

Output Specification

You are to output one line, the maximum diversity satisfying the constraints, or FIRED if Larry cannot package all the items, and loses his job.

No further constraints.

Sample Input

5 5 14
7 8 3 2 2
1 1 3 3 4

Sample Output

4