Rig Placement

Suppose we have already found where the oil is and, beyond that, we also know how much oil there is at each location. The next question is where to place the oil rigs so that, after a rig explodes, we can spill (extract) as much oil as possible. This turns out to be not completely trivial.

We model the problem as follows. There are $n$ oil fields we may want to exploit, where $1 \le n \le 100$. For each oil field we can decide how much money to invest, in increments of one million dollars, from $0$ up to $m$ (here $m$ is the maximum investment allowed per oil field). For each oil field $i$ ($1 \le i \le n$) and each investment amount $j \in {0, 1, 2, \dots, m}$, a table entry $a[i, j]$ gives the (non-negative real) amount of oil you obtain. The table entries are non-decreasing in $j$ (spending more money yields at least as much oil as before), but are otherwise arbitrary. The total budget available for rigs is an integer $B$ with $0 \le B \le 100$ (again in increments of one million dollars). Compute the maximum total amount of oil you can extract within your budget.

The first line contains the number $K$ of data sets. It is followed by the $K$ data sets, each of the following form.

The first line of a data set contains three integers $n$, $m$, and $B$: the number of oil fields, the maximum investment per oil field, and the total budget.

This is followed by $n$ lines, each containing $m + 1$ non-negative floating-point numbers. On the $i$-th line, the $j$-th number ($j = 0, 1, \dots, m$) is the amount of oil you would extract from oil field $i$ if you invested $j$ million dollars in it.

For each data set, print Data Set x: on a line by itself, where $x$ is its number. On the next line, print the maximum total amount of oil you can extract under the given constraints, rounded to two decimal places. Separate two neighboring data sets with a single blank line.