MOG Training #6Ended |
The chef of a restaurant aspiring for a Michelin star wants to display a selection of her signature dishes for inspectors. For this, she has allocated a maximum budget $B$ for the cumulated cost, and she wants to maximize the cumulated prestige of the dishes that she is showing to the inspectors.
To measure the prestige of her dishes, the chef maintains a list of recipes, along with their costs and ingredients. For each recipe, a derived dish is obtained from a base dish by adding an ingredient. The recipe mentions two extra pieces of information: the cost of applying the recipe, on top of the cost of the base dish, and the prestige the recipe adds to the prestige of the base dish. The chef measures the prestige by her own units, called ``prestige units.''
For example, a recipe list for making pizza looks like:
Here, pizza_base is an elementary dish, a dish with no associated recipe, a dish so simple that its cost is negligible (set to 0) and its prestige also 0. The chef can obtain the derived dish pizza_tomato by adding the ingredient tomato to the base dish pizza_base, for a cost of 1 euro and a gain of 2 prestige units. A pizza_classic is obtained from a pizza_tomato by adding cheese, for an added cost of 5, and a prestige of 5 added to the prestige of the base dish; this means the total cost of pizza_classic is 6 and its total prestige is 7.
A signature dish selection could for instance include both a pizza_tomato and a pizza_classic. Such a selection would have cumulated total prestige of 9, and cumulated total cost of 7.
Armed with the list of recipes and a budget $B$, the chef wants to provide a signature dish selection to Michelin inspectors so that the cumulated total prestige of the dishes is maximized, keeping their cumulated total cost at most $B$.
Important Notes
Limits
The output should consist of two lines, each with a single integer. On the first line: the maximal cumulated prestige within the budget. On the second line: the minimal cumulated cost corresponding to the maximal cumulated prestige, necessarily less than or equal to the budget.