Roll Type	Roll Length (M)	Usage (qty)
1	2.00	600
2	2.75	800
3	3.50	1200

A paper company purchases paper rolls of 8m in length and 1 m in diameter. These rolls are to be cut in various lengths. The required lengths and minimum requirements are presented in the following table.

As you can guess, each 8-meter-roll can be cut in various combinations.

In this combination an 8-meter-roll is cut into a 3.5-meter-, a 2.75 meter-long rolls. There is an excess part of 1.75m wasted as a result. In fact, this excess roll cannot be used and it needs to be sent back to the manufacturer. There is a $1500 cost for each meter of roll that is wasted.

We would like to find the best combinations of cuts and how many of each will be cut so as to minimize the total waste cost.