Population Migration

When two countries with very different economies merge, moving from the poorer part to the richer one becomes easy. Immigration quotas and border checks disappear, so leaving is only a matter of packing. Every departure changes the situation of the people who stay. There is one neighbour fewer to sell to, and one competitor fewer as well. Here you simulate that process for a single village.

Every resident works in exactly one type of job and asks a fixed price for it. Every resident also has, for each of the $m$ types of job, the largest amount of money he is willing to pay for having that job done.

A resident who buys job $k$ goes to the villager who works in job $k$ and asks the highest price that is still at most the amount the buyer is willing to pay. People want the best work they can afford rather than the cheapest offer. In two cases the resident does the job alone at no cost. First, the amount he is willing to pay for that job is 0, and then he always does it alone. Second, nobody living in the village works in that job at a price he can afford.

A resident may buy a job from himself, and that purchase counts like any other.

The income of a resident is his own price multiplied by the number of residents who buy his job from him. A resident leaves for the richer part on the day his income is strictly less than the money he could earn there. Living costs do not matter, because he would pay them in the richer part too. When several residents decide to leave on the same day, they all leave together, and everyone still in the village recomputes his income the next day from the neighbours who are left. A resident who has left never comes back, even if his old income would now be enough.

Count the residents who are still in the village once the process stops changing.

The first line contains the number of data sets $K$, with $K \ge 1$. Then $K$ data sets follow, each in the form below.

The first line of a data set contains $n$ and $m$, with $0 \le n \le 1000$ and $1 \le m \le 100$, where $n$ is the number of residents and $m$ the number of job types. Each of the next $n$ lines describes one resident and holds $m + 3$ integers $w_i$, $j_i$, $c_i$, $p_{i,1}$, $p_{i,2}$, ..., $p_{i,m}$. Here $w_i \ge 0$ is the money resident $i$ could earn in the richer part, $1 \le j_i \le m$ is the type of job he works in, and $c_i \ge 0$ is the price he asks for his work. The value $p_{i,k} \ge 0$ is the largest amount resident $i$ is willing to pay for getting job $k$ done, and a value of 0 means resident $i$ always does job $k$ alone.

No two residents work in the same job at the same price. That is, if $i \ne i'$ and $j_i = j_{i'}$, then $c_i \ne c_{i'}$.

For each data set, print Data Set x: on a line of its own, where $x$ is the number of the data set counting from 1. On the next line print the number of residents still living in the village once the process stops changing. Print a blank line after each data set.