cho.sh

Ingredients

Each dish has a minimum cost and the prestige that goes with that cheapest way; pick a subset of dishes with total cost at most B maximizing prestige, then report the smallest cost achieving it.

Medium7Dynamic programmingGraphShortest pathSortingNo attempts yetTime limit4sMemory limit512 MB

Problem

A chef who wants a Michelin star plans to present a selection of her signature dishes to the inspectors. She has a budget B for the total cost of that selection, and she wants the total prestige of the dishes she presents to be as large as possible.

The chef keeps a list of recipes together with their costs and ingredients. One recipe turns a base dish into a derived dish by adding one ingredient. A recipe also records the cost of applying it, on top of the cost of the base dish, and the prestige it adds to the prestige of the base dish. The chef counts prestige in her own unit, the prestige unit.

A recipe list for pizza looks like this.

pizza_tomato pizza_base tomato 1 2
pizza_classic pizza_tomato cheese 5 5

pizza_base is an elementary dish. No recipe produces it, so its cost is 0 and its prestige is 0. Adding tomato to pizza_base gives pizza_tomato for 1 euro and 2 prestige units. Adding cheese to pizza_tomato gives pizza_classic for 5 more euros and 5 more prestige units, so pizza_classic has total cost 6 and total prestige 7.

A selection may contain both pizza_tomato and pizza_classic. That selection has total prestige 9 and total cost 7.

Given the recipe list and the budget B, maximize the total prestige of the selection while its total cost stays at most B.

Rules

  • No dish appears twice in the selection.
  • Every dish that never appears as a derived dish is an elementary dish, with cost 0 and prestige 0.
  • A dish can appear as the derived dish of several recipes. When there is more than one way to obtain a dish, the way with the smallest total cost is the one that counts; if two ways have the same total cost, the one with the larger total prestige counts.
  • The recipes are such that no dish D can be obtained by adding one or more ingredients to D itself.

Input

  • The first line has the budget B, an integer.
  • The second line has the number N of recipes, an integer.
  • Each of the next N lines describes one recipe as five elements separated by single spaces: the derived dish name (a string), the base dish name (a string), the added ingredient (a string), the added cost (an integer), and the added prestige (an integer).

Limits

  • 0≤B≤100000 \le B \le 10000
  • 0≤N≤10000000 \le N \le 1000000
  • At most 10000 different dishes appear, elementary and derived together.
  • Every cost and every prestige written in a recipe is between 1 and 10000, inclusive.
  • Every string has at most 20 ASCII characters, using only letters, digits and the underscore.

Output

Print two lines, each with one integer. On the first line print the largest total prestige reachable within the budget. On the second line print the smallest total cost that reaches that total prestige. This cost is at most B.