Gadget Purchases

One reason health care can be so expensive is that many hospitals are equipped with very advanced — and very costly — machines. The cost of buying these machines has to be recovered somehow, typically by using them on many patients and charging each patient (or their insurance) for the usage. There are plenty of legitimate reasons to buy expensive equipment, but here we treat the purchase as a purely economic decision: figure out which machines bring in more money than they cost.

You are given a list of machines. Machine $i$ has a purchase cost $p_i$, a usage cost $c_i$, a maximum number of usages $u_i$, and a suggested charge $r_i$ that the patient (or insurance) pays per usage. You pay $p_i$ once to buy the machine and $c_i$ every time you use it, while the patient pays you $r_i$ every time. A machine can be used at most $u_i$ times: if demand is higher than $u_i$, only the first $u_i$ patients are served.

You are also given a list of patient visits; each visit names the single machine it requires. Let $d_i$ be the number of visits that require machine $i$. Then machine $i$ is actually used $s_i = \min(d_i, u_i)$ times, earning revenue $s_i \cdot r_i$ against a total expenditure of $p_i + s_i \cdot c_i$. A machine is profitable when its revenue is strictly greater than its expenditure. Determine which machines are profitable.

The first line contains the number $K$ of data sets. Then follow $K$ data sets, each of the following form.

The first line of a data set contains two integers $n$ and $m$, where $n \le 10000$ is the number of patient visits and $m \le 1000$ is the number of machines under consideration.

The next $m$ lines each describe one machine with four integers $p_i$, $c_i$, $u_i$, $r_i$.

The following $n$ lines each contain one integer $m_j$ with $1 \le m_j \le m$: the machine required by the $j$-th visit.

For each data set, first output a line Data Set x:, where $x$ is the number of the data set (starting from 1). Then output the numbers of all profitable machines, one per line, in increasing order. Separate consecutive data sets with a blank line.