Given prices for burgers, sides, and drinks, report the undiscounted total and the minimum total after forming disjoint triples where each item in a set is sold at 10% off.
Medium5GreedySortingArrayMathInterviewNo attempts yetTime limit1sMemory limit128 MBYunjin was hired at Cowburger. As a customer she had always wondered about one thing.
"Why does Cowburger have no discount on set menus?"
So she proposed a set discount. A set is one burger, one side and one drink, and each of the three products in a set is sold at 10% off its own price. A product goes into at most one set, and you choose how many sets to build.
The problem was the POS machine. Its software is so old that the Cowburger owner could not add a set discount to it, so Yunjin, who studies software engineering, decided to write the program herself. Given the prices of an order, find the total before any discount and the smallest total once the sets are grouped as favorably as possible.
The first line has the number of burgers B, the number of sides C and the number of drinks D, separated by spaces, in that order. (1≤B,C,D≤1000)
The second line has the price of each burger, separated by spaces.
The third line has the price of each side, separated by spaces.
The fourth line has the price of each drink, separated by spaces.
Every price is a multiple of 100 won and is at most 10000 won.
On the first line print the total before the set discount.
On the second line print the smallest total after the set discount. Every price is a multiple of 100, so both values are always integers.
In the first example the prices add up to 12100 won. Grouping the 3000 won burger, the 1300 won side and the 1000 won drink into one set costs 5300×0.9=4770 won, and grouping the 2500 won burger, the 1000 won side and the 500 won drink costs 4000×0.9=3600 won. The remaining 2000 won burger and 800 won side have no drink left, so they cannot form a set. The smallest total after the discount is therefore 4770+3600+2800=11170 won.