Cowburger set discount
InterviewTime limit1sMemory limit128 MB
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.
Problem
Yunjin 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.
Input
The first line has the number of burgers , the number of sides and the number of drinks , separated by spaces, in that order. ()
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 won and is at most won.
Output
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 , so both values are always integers.
Hint
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 won, and grouping the 2500 won burger, the 1000 won side and the 500 won drink costs 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 won.