Project staffing

A company wants to finish $m$ projects this week. To do that it can hire at most $n$ outside workers from an employment agency, each on a one week contract.

One outside worker is paid salary euros. If the project that the worker was put on does not finish in time, the company pays that worker nothing.

For every project the company knows from experience the probability that the project finishes within the week, as a function of how many workers are on it. The probabilities are given as percentages $p_{ij}$, where $i$ ($1 \le i \le m$) is the project number and $j$ is the number of workers on it. When nobody works on project $i$, the probability $p_{i0}$ is 0 percent.

If project $i$ finishes within the week, the company earns reward($i$) euros. If it misses the deadline, the company pays a fine of punishment($i$) euros.

Let $p$ ($0 < p < 1$) be the probability that a job finishes in time, let $E_1$ be the profit in that case, and let $E_2$ be the (negative) profit when the job is late. The expected profit for that job is $p \times E_1 + (1 - p) \times E_2$.

The company decides how many outside workers to hire and how to spread them over the projects so that the total expected profit at the end of the week is as large as possible. The optimal number of workers is the total number of people needed to reach that maximal expected profit. Compute that number. At most $n$ people are available, and a hired person works on exactly one project, so the total is the sum of the workers assigned to the projects.

The first line contains the number of test cases. Each test case has this format.

• One line with the number of projects $m$. ($1 \le m \le 100$)
• One line with the maximal number of available workers $n$. ($0 \le n \le 100$)
• One line with salary, the pay of one worker in euros. salary is an integer between 0 and 1000.
• $m$ lines, one per project. Line $i$ holds $n$ integers $p_{i1}, p_{i2}, \dots, p_{in}$, followed by reward and punishment for project $i$. Every percentage is an integer between 0 and 100, and reward and punishment are amounts in euros between 0 and 100000. All values on a line are separated by single spaces.

Print two lines for every test case.

• The first line holds the maximal expected profit in eurocents. The percentages are whole numbers and the amounts are whole euros, so this value is always an integer number of eurocents.
• The second line holds the total number of outside workers that must be hired to reach that maximal expected profit. If several different totals reach it, print all of them in increasing order, separated by single spaces.