Communication

Time Limit : 5 seconds Memory Limit : 10MB

We have received an order to build a communication system on the Earth. The system consists of several cities connected with some on-ground and under-ground communication paths.

In this problem, we assume that the Earth is a perfect sphere with a radius of exactly 6378 km. On-ground paths are built on the surface of the earth, while under-ground paths are straight lines which pass through the earth.

As you know, constructing under-ground paths is a difficult job. Only K or less than K paths are allowed to build. However, you can build unlimited number of on-ground paths.

Your task is to construct some paths for given cities so that any two cities are connected by the paths directly or indirectly. For economic reasons, the total length of the path should be minimized.

The value of PI is approximately 3.141592653589793.

Input:

The input contains several cases.

The first line contains two numbers N (1 <= N <= 500) and K (0 <= K < N). The following N lines describe the locations of the N cities. Each line contains two real numbers, representing its latitude and longitude.
The latitude will be between -90 and +90. The longitude will be between -180 and +180 where negative numbers denote locations west of the meridian and positive numbers denote locations east of the meridian.

The input ends with a zero on a single line.

Output:

For each case, output a number representing the total length (km) of the paths, rounded to the nearest integer.

Sample Input:

2 0
-90.00 0.00
90.00 0.00
2 1
-90.00 0.00
90.00 0.00
0

Sample Output:

20037
12756