Maximum Number of Complete Recipes

You are given a set of recipes and a list of available ingredients. Each recipe is defined by a name and a list of required ingredients with specific quantities. Your task is to determine the maximum number of complete recipes that can be prepared using the available ingredients. In each step, you may choose any recipe that can be prepared with the current stock of ingredients, deduct the required quantities upon preparation, and count it as one complete recipe. The process is repeated until no recipe can be fully prepared.

Mathematically, for each recipe \(r\) that requires ingredients \(\{(i, q_{i})\}\) and for a given available stock \(A(i)\) for each ingredient \(i\), you can prepare recipe \(r\) if and only if \[ A(i) \geq q_{i}\quad \text{for every ingredient } i \text{ in } r. \] After preparing a recipe, the ingredient stock is updated as follows: \[ A(i) \leftarrow A(i) - q_{i}, \quad \forall i \text{ in } r. \] The goal is to maximize the count of recipes prepared.

inputFormat

The input is read from stdin and has the following format:

R
recipe_name1 n ingredient1 qty1 ingredient2 qty2 ...
recipe_name2 n ingredient1 qty1 ingredient2 qty2 ...
... (R recipes in total)
I
ingredient1 qty1
ingredient2 qty2
... (I ingredients in total)

Where:

• R is an integer representing the number of recipes.
• For each recipe: recipe_name is a string, n is the number of ingredients required for that recipe, followed by n pairs of (ingredient name and required quantity).
• I is an integer representing the number of types of ingredients available.
• Each of the next I lines contains the name of the ingredient and its available quantity.

outputFormat

Output a single integer to stdout which represents the maximum number of complete recipes that can be prepared using the available ingredients.

3
pasta 2 tomato 2 cheese 1
burger 2 bread 1 patty 2
salad 3 lettuce 1 tomato 1 dressing 1
6
bread 1
patty 2
tomato 3
cheese 1
lettuce 1
dressing 1

2