R. Oil Fields
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Because climate change is a hoax $$$^{\text{[citation needed]}}$$$, Alice has decided to enter the lucrative business of oil drilling. There are $$$n$$$ deposits of oil scattered across the $$$2$$$-d coordinate plane, numbered $$$1$$$ through $$$n$$$. The $$$i$$$-th deposit is at coordinate $$$(x_i, y_i)$$$ and has $$$w_i$$$ units of oil.

Alice can enclose some oil deposits with a perimeter to secure drilling rights. The profit from such a perimeter is the total amount of oil minus the cost of the perimeter. The cost of a perimeter of length $$$k$$$ is given by the expression $$$m\dot k+c$$$, where $$$m$$$ and $$$c$$$ are given constants. Help Alice find the maximum profit she can make.

Input

Each test contains multiple testcases. The first line contains the number of testcases $$$t$$$ ($$$1\leq t\leq 20$$$). The description of the test cases follows.

The first line of each testcase contains three integers $$$n$$$,$$$m$$$,and $$$c$$$ ($$$1\leq n\leq 400$$$, $$$0\leq m,c\leq 10^9$$$) — the number of oil deposits and the parameters of the cost function, as described above.

The $$$i$$$-th of the next $$$n$$$ lines contains three integers $$$x_i,y_i,w_i$$$ ($$$\lvert x_i\rvert, \lvert y_i\rvert\leq 10^9, 1\leq w_i\leq 10^9$$$) — the location and amount of oil of the $$$i$$$-th deposit. Note that the positions of deposits may not be distinct.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$500$$$.

—

Testcases in subtasks are numbered $$$1$$$ to $$$40$$$ with samples skipped.

Test $$$1-6$$$: The sum of $$$n$$$ does not exceed $$$20$$$.

Test $$$7-12$$$: All $$$w_i$$$ have the same value.

Test $$$13-40$$$: No additional constraints.

The test are worth an alternating $$$2$$$ or $$$3$$$ points with samples skipped.

Output

For each test case, print a single floating point value — the maximum profit that Alice can earn by building one perimeter.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Examples
Input
1
3 10 0
1 1 5
2 6 3
5 5 1
Output
5.000000
Input
3
2 2 0
1 1 100
3 3 100
4 0 0
1 1 1
2 4 1
4 2 1
4 4 1
3 1 100
1 1 2
1 2 2
2 1 2
Output
188.686292
4.000000
-97.414214
Input
3
6 2 5
1 1 5
4 3 2
2 5 3
5 6 6
3 4 7
4 5 3
6 3 1
6 4 5
5 4 4
7 5 3
1 1 1
6 3 5
7 1 6
15 2 10
7 5 2
1 3 9
2 5 10
5 4 13
2 6 17
1 1 11
11 2 3
3 4 3
4 2 12
6 9 1
2 7 1
10 8 3
3 3 8
1 5 14
11 5 2
Output
2.000000
5.000000
58.163779
Note

Problem Idea: dutin Problem Preparation: dutin Occurrences: Advanced 11