50056. How Much Money Can You Make?

I'm a slow walker, but I never walk backwards.

Task Description

Given the amount and unit prices of the $N$ types of raw materials, and the ingredients and selling prices of $M$ products, write a program to determine the most profitable product.

Let us illustrate the task with an example. If we are given four types of raw materials, soybean, wheat, sugar, oil. Their amount are 160, 170, 70, and 80 respectively. Their unit prices are 4, 3, 1 and 2 respectively. It is possible to produce four products, douhua, bread, stinky tofu, steamed bun from these materials.

  • A douhua needs 8 units of soybean, 3 units of sugar, and is selling at 40 dollars.
  • A bread needs 6 units of wheat, 5 units of sugar, 4 units of oil, and is selling at 38 dollars.
  • A stinky tofu needs 7 units of soybean, 8 units of oil, and is selling at 55 dollars.
  • A steamed bun needs 8 units of wheat, and is selling at 28 dollars.

We now find the most profitable product to produce. Note that all products are profitable and we will choose exactly one to produce. If we produce douhua, then we can produce 20 of them. Since the the cost to produce a douhua is 35, the selling price is 40, the profit per douhua is 5, and the total profit to produce douhua is 100. Similarly the total profits to produce bread, stinky tofu, and steamed bun are 98, 110, and 84 respectively. Therefore, If we produce stinky tofu, we will earn the maximum profit 110.

Input Format

Each test case starts with two integers $N$ and $M$, indicating the number of raw material types and the number of products.

The following $N$ lines describe the raw materials. Each line contains a string and two integers $X$, $Y$, indicating the name, the amount and the unit price of a raw material.

Then, the following lines describe the $M$ products.
For each product, the first line contains a string and an integer $Q$, indicating the name and the number of raw materials used in the product.
For the following $Q$ lines, each line contains a string and an integer, indicating the name of a raw material and the amount of the raw material used in that product.
Finally, there is one line containing an integer $P$, representing the selling price of the product.

Limitation

  • $1 ≤ N ≤ 100$
  • $1 ≤ M ≤ 100$
  • 1 ≤ $X$ ≤ 10000
  • 1 ≤ $Y$ ≤ 100000
  • 1 ≤ $Q$ ≤ N
  • 1 ≤ $P$ ≤ 100000
  • 1 ≤ the length of a raw material name ≤ 50
  • 1 ≤ the length of a product name ≤ 50
  • There is no whitespace in each of the names.

Output Format

For each case, print the name of the most profitable product and the profit we will earn. If there are multiple most profitable products, print the one with the smallest lexicographical order.

  • 1 ≤ the maximum profit ≤ 1000000

Sample Input

4 4
soybean 160 4
wheat 170 3
sugar 70 1
oil 80 2
douhua 2
soybean 8
sugar 3
40
bread 3
wheat 6
sugar 5
oil 4
38
StinkyTofu 2
soybean 7
oil 8
55
SteamedBun 1
wheat 8
28

Sample Output

StinkyTofu 110

Discussion