The Plane Problem

Time Limit: 10 Seconds    Memory Limit: 32768 KB
Special Judge

Air transportability is concerned with the packing of cargo on aircraft. In order to ensure safe takeoffs and landings, cargo must be packed according to rigorous rules, which can vary from airplane to airplane. Rules for packing aircraft are:

  • All aircraft will have weight limits. They cannot hold more than their weight limit, and for the sake of efficiency, no plane may carry less than 50% of its weight limit.
  • Cargo items are rectangular and have uniform weight distribution. Two adjacent items must be at least 1 foot apart to allow for tie downs.
  • All aircraft will have a rectangular area for cargo, the cargo hold. No cargo can be placed within one foot of the edge of the cargo hold to allow space to tie it down.
  • At least 60% of the cargo weight must be put in the front half of the cargo hold.
  • The weight on the left side of the center line must be no more than 5% more or less than the weight on the right hand side of the center line.
  • If a piece of cargo can be moved toward the rear of the plane and still meet the other constraints, then it should be moved toward the rear of the plane because all loading and unloading takes place at the rear of the plane.
  • To allow for speedy loading and unloading, no plane may hold more than 10 items.

You are to write a program to help allocate cargo to aircraft efficiently.

Input

The input will consist of one or more input sets. The first line of each input set will be an integer 0 <= p <= 10 which represents the number of planes to be loaded. There will then be p sets of plane information. Each set of plane information has two lines. The first has a string of 1 to 25 characters representing the name of the aircraft. No two different aircraft in an input set will have the same name. The second line will have four integers, 0 < x <= 100, 0 < y <= 30, 0 < w <= 100000, 0 < c <= 20000 where:

  • x represents the length of the cargo hold (from the front of the plane to the rear of the plane) in feet,
  • y represents the width of the plane (from left to right) in feet,
  • w represents the weight limit of the plane in pounds,
  • c represents the cost of the plane in dollars.

After the plane information will be the information about the cargo to be loaded. The first line will have a single integer 0 < n <= 10, representing the number of pieces of cargo to be loaded. There will then be n sets of cargo item information. Each line of cargo information will consist of 4 integers 0 < i <= 1000, 0 < len <= 20, 0 < wid <= 20, 0 < wt <= 10000, where:

  • i is a unique value that identifies the cargo item and gives its relative priority (where the higher the value, the more important the item)
  • len is the length of the item in feet
  • wid is the width of the item in feet
  • wt is the weight of the item in pounds

Items cannot be turned when they are loaded on the aircraft, so the lengthwise side of the cargo item must be loaded lengthwise along the aircraft. The end of input will be a set with p = 0. This set should not be processed.

Output

If it is possible to load all of the cargo meeting the constraints, you should load the cargo using the most inexpensive collection of planes, given the constraints above. If all of the cargo cannot be loaded, you should load as many items as possible without regard for cost. If two configurations load the same number of items, select the configuration with the highest total priority. If two configurations have the same number of items loaded and the same priority and meet all of the above constraints, print either one.

The first line of output for each input set should include the number of the set (starting with 1) and the total cost of the planes used to transport the set. Then, for each plane used, give the name of the plane on a line by itself followed by one line for each of the cargo items on the plane (in ascending numerical order of priority), giving the cargo item number, and the distance of its leftmost front corner from the front of the cargo hold and the left edge of the cargo hold (because of the position of tie downs, these must be integer values). Finally, on the last line of the output, if there are pieces of cargo that cannot be loaded, list them, in numerical order of priority.

Have a blank line after each input set and use the format in the sample output.

Sample Input

2
C-5A, first
100 30 100000 20000
Cessna
10 5 1000 200
5 
400 20 20 56000
300 20 20 4000
80 20 10 30000
900 20 10 10000
5 5 3 400
0

Sample Output

Plane loading 1:
C-5A, first
    80 loaded at 79 back, 1 from left
    300 loaded at 30 back, 5 from left
    400 loaded at 9 back, 9 from left
    900 loaded at 79 back, 19 from left

Unloaded: 5
Submit

Source: Southeast USA 2000