Problem B
Ingredients
![\includegraphics[width=.6\textwidth ]{ingredients}](/problems/ingredients/file/statement/en/img-0001.png)
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
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:
-
pizza_tomato pizza_base tomato 1 2
-
pizza_classic pizza_tomato cheese 5 5
Here, pizza_base is an
elementary dish, a dish with no associated recipe, a
dish so simple that its cost is negligible (set to
A signature dish selection could for instance include both a
pizza_tomato and a pizza_classic. Such a selection would have
cumulative total prestige of
Armed with the list of recipes and a budget
Important Notes
-
No dish can appear more than once in the signature dish selection.
-
Any dish that does not appear as a derived dish in any recipe is considered to be an elementary dish, with cost
and prestige . -
A dish can appear more than once as a resulting dish in the recipe list; if there is more than one way to obtain a dish, the one yielding the smallest total cost is always chosen; if the total costs are equal, the one yielding the highest total prestige should be chosen.
-
The recipes are such that no dish
can be obtained by adding one or more ingredients to itself.
Input
-
The first line consists of the budget
, an integer. -
The second line consists of the number
of recipes, an integer. -
Each of the following
lines describes a recipe, as the following elements separated by single spaces: the derived dish name (a string); the base dish name (a string); the added ingredient (a string); the added price (an integer); the added prestige (an integer).
Limits
-
; -
; -
there can be at most
different dishes (elementary or derived); -
costs and prestiges in recipes are between
and (inclusive); -
strings contain at most
ASCII characters (letters, digits, and ’_’ only).
Output
The output should consist of two lines, each with a single integer. On the first line: the maximal cumulative prestige within the budget. On the second line: the minimal cumulative cost corresponding to the maximal cumulative prestige, necessarily less than or equal to the budget.
Sample Input 1 | Sample Output 1 |
---|---|
15 6 pizza_tomato pizza_base tomato 1 2 pizza_cheese pizza_base cheese 5 10 pizza_classic pizza_tomato cheese 5 5 pizza_classic pizza_cheese tomato 1 2 pizza_salami pizza_classic salami 7 6 pizza_spicy pizza_tomato chili 3 1 |
25 15 |