The Merchant of Venice

Time limit2sMemory limit512 MB

Summary

Sum the cargo values of all ships whose distance is at most s*d, the distance they can cover by the due date.

Level: Easy1 of 10
Topics: Implementation, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples5

Example 1

Input

Expected output

Data Set 1:
191

Data Set 2:
3

Example 2
Input
```
1
0 1 1
```
Expected output
```
Data Set 1:
0
```

Example 3

Input

1
3 1 1
2 5
10 100
10000 100000

Expected output

Data Set 1:
0

Example 4

Input

1
4 100 99
9900 100000
9899 1
9901 99999
0 0

Expected output

Data Set 1:
100001

Example 5

Input

Expected output

Data Set 1:
7

Data Set 2:
0

Data Set 3:
10

Data Set 4:
100000

Data Set 5:
4