Radha's Shop Sales

Problem Statement

Radha's Shop Sales Radha runs a paint shop. She has three basic colours in stock: X units of Red, Y units of Blue and Z units of Green. Any unit of a basic colour can be sold as it is for M rupees. She can also boil basic colours together to produce a synthetic colour. Each mixture consumes whole units and produces one unit of the result: Purple : 1 Red + 1 Blue gives 1 Purple, sold for P rupees. Teal : 1 Blue + 1 Green gives 1 Teal, sold for Q rupees. Black : 1 Red + 1 Blue + 1 Green gives 1 Black, sold for R rupees. A unit consumed by a mixture cannot also be sold on its own, and there is no partial mixing. Decide how many units of each synthetic colour to make so that the total money from everything sold -- synthetic colours plus the basic units that are left -- is as large as possible. Input Format The first line contains an integer T , the number of instances. Each instance is two lines: three space-separated integers X , Y , Z -- the units of Red, Blue and Green; four space-separ