Plot

Memory limit: 64 MB

We call any sequence of points in the plane a plot. We intend to replace a given plot with another that will have at most points () in such a way that it "resembles" the original plot best.

The new plot is created as follows. The sequence of points can be partitioned into () contiguous subsequences:

where , and afterwards each subsequence , for , is replaced by a new point . In that case we say that each of the points has been contracted to the point . As a result a new plot, represented by the points , is created. The measure of such plot's resemblance to the original is the maximum distance of all the points to the point it has been contracted to:

where denotes the distance between and , given by the well-known formula:

An exemplary plot and the new plot , where are contracted to , whereas to .

For a given plot consisting of points, you are to find the plot that resembles it most while having at most points, where the partitioning into contiguous subsequences is arbitrary. Due to limited precision of floating point operations, a result is deemed correct if its resemblance to the given plot is larger than the optimum resemblance by at most .

Input

In the first line of the standard input there are two integers and , , separated by a single space. Each of the following lines holds two integers, separated by a single space. The -th line gives , , denoting the coordinates of the point .

Output

In the first line of the standard output one real number should be printed out, the resemblance measure of the plot found to the original one. In the second line of the standard output there should be another integer , . Next, the following lines should specify the coordinates of the points , one point per line. Thus the -th line should give two real numbers and , separated by a single space, that denote the coordinates of the point . All the real numbers should be printed with at most 15 digits after the decimal point.

Example

For the input data:

7 2
2 0
0 4
4 4
4 2
8 2
11 3
14 2

the correct result is:

3.00000000
2
2.00000000 1.76393202
11.00000000 1.99998199

Task author: Jakub Pawlewicz.