DotR Equipment Synthesis Optimization

In the game DotR (Defense of the Robots) Allstars, every hero has one attribute: strength. A hero can increase his strength by acquiring equipment. Each equipment gives a fixed amount of strength. There are two types of equipment: basic items, which can be bought directly from the store with coins (each with a limited supply), and advanced items which must be synthesized (i.e. combined) from other items (basic or lower‐tier advanced items) according to a synthesis tree. Synthesis does not cost extra coins but consumes the component items. When items are purchased, their strength values contribute to the hero’s total strength. However, when you synthesize an advanced equipment, you lose the contribution of its components and gain instead the advanced equipment’s strength value. In other words, if the sum of the basic values of the ingredients is B and the advanced item’s strength is A, then synthesizing yields an extra bonus of A − B (which might be negative, so you only want to synthesize when beneficial).

You are given:

• An integer M representing the total coins available.
• B basic equipment types. Each basic equipment is described by its name (a string without spaces), coin cost, available quantity, and strength value.
• R recipes for advanced equipment. Each recipe has a unique name, an advanced strength value, and a list of K ingredients (each ingredient is referenced by its name). Note that the synthesis tree is given in topologically sorted order, meaning that when a recipe appears, all of its ingredient items have been defined earlier (either as a basic item or via another recipe).

Your task is to help hero Spectre maximize his total strength. He can decide how many copies of each basic equipment to buy (without exceeding each equipment’s available quantity and his coin budget M). Initially, every purchased basic equipment contributes its strength value to his total strength. Then, for any advanced equipment synthesis you perform, you must remove exactly one copy of each required ingredient from your inventory and you will add the advanced equipment in their place. In effect, synthesis converts the sum strength of the ingredients into the advanced equipment’s strength. You may apply each recipe as many times as allowed by your inventory. Compute the maximum total strength value Spectre can obtain.

Note: If an advanced recipe’s bonus (advanced strength minus the sum of the basic strengths of its ingredients) is not positive, it is not beneficial to perform the synthesis.

inputFormat

The input begins with an integer M (1 ≤ M ≤ 10⁴), the total coins available.

Then an integer B (1 ≤ B ≤ 10) is given, representing the number of basic equipment types. The following B lines each contain:

name cost quantity strength

where name is a string without spaces, and cost, quantity and strength are positive integers.

Next, an integer R (0 ≤ R ≤ 10) is given, the number of advanced equipment recipes. Each of the next R recipes is described in two lines. The first line contains:

name advanced_strength K

where name is the advanced equipment’s name (a string without spaces), advanced_strength is a positive integer, and K (≥ 1) is the number of ingredients required. The second line contains K space‐separated strings, each being the name of an ingredient. (It is guaranteed that every ingredient has been defined earlier either as a basic equipment or as an advanced equipment recipe.)

outputFormat

Output a single integer – the maximum total strength value that can be obtained.

sample

10
3
OgreAxe 3 3 4
BeltStrength 2 2 3
RecipeScroll 1 4 1
1
Sange 10 3
OgreAxe BeltStrength RecipeScroll

14