Stimulus Package

To ease the impact of an economic crisis, a government passes a large stimulus package: rather than waiting for private investors, it funds worthwhile projects that also create jobs. Deciding which projects to fund is hard, because projects differ in how many jobs they create, how much they cost, and how much lasting infrastructure they leave behind. Some projects create jobs right away (like building a bridge), while others create them only in later years (like research).

Each project $i$ has a cost $c_i$, an infrastructure gain $g_i$, and a job-creation profile $j_{i,1}, j_{i,2}, \ldots, j_{i,Y}$ giving the jobs it creates in each of the next $Y$ years. You are also given a total budget $B$ and yearly job-creation targets $J_1, J_2, \ldots, J_Y$.

Choose a set $S$ of projects whose total cost does not exceed $B$ and whose combined job creation is at least $J_t$ in every year $t$ (that is, $\sum_{i \in S} j_{i,t} \ge J_t$ for all $t$). Among all such sets, report the maximum possible total infrastructure gain $\sum_{i \in S} g_i$. If no set meets every yearly job-creation target within the budget, report that instead.

The first line contains the number $K$ of data sets. Each data set has the following form:

• The first line contains three integers $n$, $Y$, and $B$: the number of projects $n \le 20$, the number of future years $1 \le Y \le 50$, and the total budget $0 \le B \le 10^9$.
• The next line contains $Y$ integers, the yearly job-creation targets $J_1, \ldots, J_Y$.
• Each of the following $n$ lines describes one project with $Y + 2$ integers: the job-creation numbers $j_{i,1}, \ldots, j_{i,Y}$, then the project's cost $c_i$, then its infrastructure gain $g_i$.

For each data set, print a line Data Set x:, where x is the data set's number (starting from 1). On the next line print either No selection. if no set meets every yearly job-creation target within the budget, or the maximum total infrastructure gain otherwise. Separate consecutive data sets with a blank line.