Buying Pumpkins

Halloween is coming, and we are going to a Pumpkin Patch to buy some pumpkins to carve Jack-o'-lanterns.

Every pumpkin can be considered an ellipse:

pumpkin-ellipse

For this problem, all you need to know about an ellipse is that if its width is $2 \cdot a$ and its height is $2 \cdot b$ , then its area is $π \cdot a \cdot b$ (Pi times $a$ times $b$ ).

There are $N$ pumpkins available for purchase at the Pumpkin Patch. Each of them has its price, height, and width. We have a total of $D$ dollars and want to purchase 2 pumpkins. What is the maximum total area of the 2 pumpkins we can buy?

Note that we must buy 2 pumpkins, even if there is a single pumpkin whose area is larger.

Input

The first line contains an integer $T$ — the number of test cases.

Each test case starts with a line containing two integers $N$ and $D$ . Each of the following $N$ lines contains 3 integers $P_{j}$ , $H_{j}$ , $W_{j}$ - the price (in dollars), height, and width of pumpkin $j$ .

Constraints

$2 \leq N \leq 50$
$2 \leq D \leq 100$
$1 \leq P_{j} < D$
$1 \leq H_{j}, W_{j} \leq 100$
There is at least one pair of pumpkins that can be purchased with $D$ dollars.

Output

For each test case, print a single line Case #i: area, where area is the maximum possible total area of 2 pumpkins that fit into budget $D$ .

Your answer must have an absolute or relative error of at most $1 0^{- 6}$ from the correct value.

Examples

Input

Output

Case #1: 15.707963
Case #2: 47.909288
Case #3: 28.274333

Explanation

Case 1. We have 5 dollars, and there are 3 pumpkins:

A pumpkin with height 4 and width 4 that costs $3. Its area is $π \cdot (4/2) \cdot (4/2)$ .
A pumpkin with height 5 and width 3 that costs $4. Its area is $π \cdot (5/2) \cdot (3/2)$ .
A pumpkin with height 2 and width 2 that costs $1. Its area is $π \cdot (2/2) \cdot (2/2)$ .

The optimal purchase here is to buy the first and third pumpkin, for a total area of $5 \cdot π$ .

Case 2. There are two pumpkins, both of which we can purchase with our $10.

Case 3. Even though a single pumpkin with height and width of 100 would produce a higher total area, we want to purchase specifically two pumpkins. The optimal purchase here is the second ($3) and fifth ($7) pumpkins.