Cherry Picking

Insurance began as a simple idea: everyone pays money into a common pool so that, if one or a few members suffer a calamity they could not afford on their own, there is enough money to cover them. As participation grew, administration became more complex and more rules were needed. Eventually people argued that this administration would run far more efficiently under private companies motivated by profit. But once a private insurer tries to maximize profit, its incentives change: it has the least interest in covering exactly the people who need insurance most, such as the elderly or patients with pre-existing conditions. Choosing to insure only the most profitable individuals is known as cherry picking. In this problem you will write a program that cherry-picks well.

You are given a list of $n$ patients, each belonging to one of $C$ categories (for example, "male, 18-30" or "female, 25-40"). For every patient you know the maximum premium they can afford per year and the amount of benefits you expect to pay them per year. For each category $c$ you may set a single premium $p_c$. Within category $c$, every patient whose affordable amount is at least $p_c$ becomes insured: they pay you $p_c$ per year, and in return you must pay their benefits. Patients who cannot afford $p_c$ go elsewhere and are not insured.

Your profit is the total premiums collected minus the total benefits paid. You want to choose the premiums to maximize this profit. However, a regulator requires that you insure at least $m$ patients in total, so your choice of premiums must insure at least $m$ people.

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

The first line of a data set contains three integers $n$, $C$, and $m$: $1 \le n \le 1000$ is the number of patients, $1 \le C \le 30$ is the number of categories, and $0 \le m \le n$ is the minimum number of patients you must insure.

Each of the next $n$ lines describes one patient $i$ with three integers $c_i$, $p_i$, and $b_i$: $1 \le c_i \le C$ is the patient's category, $p_i \ge 0$ is the maximum premium the patient can afford, and $b_i \ge 0$ is the benefits you must pay that patient.

For each data set, print a line Data Set x:, where $x$ is the 1-based index of the data set. On the following line print a single integer: the maximum profit you can make by choosing one premium per category while insuring at least $m$ patients. Separate consecutive data sets with a single blank line, and do not print a blank line after the last data set. The maximum profit may be negative.