S - Greedy Contractor

Asphalt, Cement and Marmelade, Inc. (ACM) specializes in building paved roads. They have been hired by a very rich client to build a network of highways to connect n cities. They want to make as much profit as possible by building a network of roads of the largest possible total length. However, the client is not stupid and will not approve a plan if there are redundant roads - there must be one and only one path between any pair of cities. As long as this condition is met, the client will pay d dollars per meter of road. Your task is to determine the largest profit that can be made, given the locations of the cities.

The roads are allowed to intersect. If this happens, a bridge will be built at no extra cost to you. In other words, do not worry about intersecting roads.

Input

Input will consist of a number of test cases. Each test case will begin with two numbers on a line - n and d. The next n lines will each contain a pair of integers (the x- and y-coordinates of a city, in kilometers).

0<=n<=50, 0<=d<10000. Each city will be located in the square [-10000, 10000]², so the largest distance between any two cities is 20000*sqrt(2).

Output

For each test case, output a line with the largest amount of money the client will pay, rounded to the nearest integer.

Sample input

2 1
0 0
3 4
3 2
0 0
0 3
4 0
4 10000
-10000 10000
10000 -10000
10000 10000
-10000 -10000

Sample output

$5000
$18000
$765685424949