Request for Proposal

When a government, military, or commercial agency wishes to make a major purchase, it first issues a Request for Proposal (RFP) that lists a number of requirements a successful proposal must meet. Competing suppliers submit Proposals, each indicating which of the requirements it meets and the price that will be charged if the agency accepts the proposal.

Because these agencies are staffed by bureaucrats and are accountable to other agencies staffed by bureaucrats, all human judgement must be removed from the selection process. To that end, each evaluator is given a feature sheet: one column per requirement, one extra column for the price, and one row per Proposal. The evaluator reads each proposal and places a check mark in the cell for every requirement it meets. After all proposals are evaluated, the number of check marks in each row is summed. A proposal whose number of check marks equals the number of requirements is called compliant; otherwise it is partially compliant.

Many agencies award the contract to the lowest compliant proposal — the compliant proposal with the lowest price. If there is no compliant proposal, many agencies measure partial compliance with the following formula:

$$\text{compliance} = \frac{\text{number of requirements met}}{\text{number of requirements}}$$

Your job is to select the Proposal with the highest compliance. If several proposals share the highest compliance, choose the one with the lowest price. If several proposals share the same compliance and the same price, choose the one that appears first in the input.

The input consists of the information for a number of RFPs and their associated proposals. The information for each RFP consists of:

• A line with two integers: $n$ ($0 < n \le 1000$), the number of requirements, and $p$, the number of proposals. A line containing 0 0 indicates there are no more RFPs.
• $n$ lines naming the requirements. Each requirement is a string of up to 80 characters, terminated by the end of the line. All strings are case sensitive.
• For each of the $p$ proposals:
  • A line naming the proposal (up to 80 characters, terminated by the end of the line).
  • A line containing a floating-point number $d$ and an integer $r$ ($0 \le r \le n$): $d$ is the price and $r$ is the number of met-requirement lines that follow.
  • For each met requirement, its name on its own line. Every such requirement comes from this RFP's requirement list, and no requirement is repeated.

For each RFP, print the number of the RFP (see the sample) followed by the name of the best proposal according to the criteria above. Print a blank line between the output for consecutive RFPs.