The Merchant of Venice

Shakespeare's play The Merchant of Venice has one of the more interesting villains in Shylock, a Jewish moneylender who has been hurt many times and in different ways by Christians in general and by Antonio, the merchant of the title, in particular. When Antonio's friend Bassanio urgently needs to borrow 3000 ducats to woo the lady he loves, Antonio's money is tied up in his trading fleet. Instead of lending it himself, Antonio signs a loan contract with Shylock that promises a pound of his own flesh if the 3000 ducats are not repaid by the due date. His fleet is lost in a storm, and the story turns ominous.

We ignore here the risk analysis Antonio should probably have carried out, asking how likely each of his ships was to return and what the probability was that he would fail to repay the money by the due date. We only ask how much money Antonio can repay Shylock by a given date, depending on where his ships are when the contract is signed.

You are given the number of days until the due date and the speed at which the ships travel. For each ship you are also given its distance from Venice and the value of its load in ducats. Output the number of ducats Antonio can repay by the due date.

The first line contains the number of data sets in the file, $K \ge 1$. It is followed by $K$ data sets of the following form.

The first line of a data set contains three integers $n$, $s$, $d$. Here $0 \le n \le 200$ is the number of ships Antonio owns, $1 \le s \le 100$ is the speed of the ships in miles per day, and $1 \le d \le 365$ is the number of days until the contract's due date.

This is followed by $n$ lines, each containing two integers $d_i$, $v_i$. Here $0 \le d_i \le 10000$ is the distance of ship $i$ from Venice in miles, and $0 \le v_i \le 100000$ is the value of ship $i$'s load.

For each data set, first output Data Set x: on a line by itself, where $x$ is the number of the data set. On the next line, output the total number of ducats that Antonio can repay Shylock after $d$ days. If a ship arrives exactly after $d$ days, Antonio may already use its cargo for the repayment.

Follow each data set with one blank line.