Privacy Loss

At the heart of much of the ethical debate over whether the government should be allowed to spy on its citizens is the question of whether "privacy" is worth preserving at all. That is a separate question from the legal debate over whether current law already permits it. People who favor government spying often argue that the only ones who want privacy are the ones planning something illegal. Ask those same people a few very personal questions about what they do behind closed doors, and the argument tends to evaporate. Much of privacy is really about protecting behavior that is not illegal but that others may not appreciate, so we would rather they not know. Wide circulation of your most heartfelt love letter, or of a picture of you passed out on the couch drooling after a hard day at work, would embarrass most people badly.

The trouble is that nearly every measure proposed in the name of security buys its security with a privacy cost and a cost in money or effort. Putting a camera in every room of every house and apartment and analyzing the video would prevent some crimes and some terrorist attacks, but it would also invade privacy on a huge scale, and it would cost a fortune. Reading every e-mail that goes out is a somewhat smaller invasion, cheaper, and correspondingly less effective. Designing an "acceptable" set of programs therefore means weighing the privacy loss and the money against the security gained.

You are given a list of surveillance options, each described by its security benefit, its privacy cost, and its financial cost. You are also given a financial budget and the total level of privacy invasion society is willing to accept. Determine the largest total security benefit obtainable without violating either limit.

Each option is either taken or not taken, and no option may be taken twice.

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

The first line of a data set contains three integers $n$, $B$, $P$ separated by spaces. $1 \le n \le 100$ is the number of surveillance options under consideration, $0 \le B \le 100$ is the total budget for surveillance, and $0 \le P \le 100$ is the largest total privacy cost society finds acceptable.

Then come $n$ lines, each containing three integers $s_i$, $c_i$, $p_i$. $0 \le s_i \le 1000$ is the security benefit of option $i$, $0 \le c_i \le 100$ is the cost of option $i$, and $0 \le p_i \le 100$ is its privacy loss.

For each data set, print Data Set x: on a line by itself, where $x$ is the number of that data set counting from 1. On the next line print the largest total security benefit that can be gained without violating the budget or the privacy limit. Print one blank line between consecutive data sets, and no blank line after the last one.