Dr. Zoidberg is a famous cardiologist and comedian that likes to make unpleasant jokes. One of his favorite jokes is to adulterate cardiograms to make people believe they will die. A cardiogram is defined as the diagram of a polyline described with a list of N points (x1, y1), (x2, y2), . . . , (xN , yN ) with ascending x-coordinates, whose line segments are drawn between consecutive points. The length of a cardiogram is defined as the sum of the lengths of each segment drawn on it: N−1√ ∑ i=1 (xi+1 − xi)2 + (yi+1 − yi)2 The technique used by Dr. Zoidberg to adulterate a cardiogram consists of removing exactly K points from its polyline, where K depends on the seriousness of the patient. Of course, there could be several ways to do that, but the joke will be the best (in Zoidberg’s opinion!) if the resulting plot is as short as possible in the sense that it becomes a good approximation to a straight line, that is, if it makes the patient believe he or she is close to death. To avoid suspicion, Dr. Zoidberg does not remove neither the first point nor the last point from the polyline. The cardiogram of a healthy patient. Length: 36.393. The cardiogram of a healthy patient. Length: 36.393. The first cardiogram removing some K = 9 points. Length: 20.000. The last cardiogram corresponds to a patient who may believe he or she possibly will die. Dr. Zoidberg wants to know the minimum length that can be attained adulterating a cardiogram described by the polyline with points (x1, y1), (x2, y2), . . . , (xN , yN ), removing exactly K points from that polyline. May you help him?
2/2 Input The input consists of several test cases. The first line of a test case contains two blank-separated integers N and K, where N is the number of points on the polyline describing the cardiogram (2 ≤ N ≤ 256), and K is the number of points that Dr. Zoidberg must remove from that polyline (0 ≤ K ≤ N−2). Then follow N lines: line i contains exactly two blank-separated integers xi and yi, where (xi, yi) is the position of the i-th point of the polyline describing the cardiogram (0 ≤ xi < 1000, −1000 < yi < 1000). You may assume that the points of the polyline have ascending x-coordinates (i.e., x1 < x2 < · · · < xn). Output For each test case, print a single line with the minimum length that can be attained adulterating the cardiogram using Dr. Zoidberg’s technique. The answer should be formatted and approximated to three decimal places. The floating point delimiter must be ‘.’ (i.e., the dot). The rounding applies towards the nearest neighbor unless both neighbors are equidistant, in which case the result is rounded up (e.g., 78.3712 is rounded to 78.371; 78.5766 is rounded to 78.577; 78.3745 is rounded to 78.375, etc.). Sample Input 11 2 00 50 6 -2 73 8 -3 90 11 0 12 1 13 -2 14 0 20 0 11 9 00 50 6 -2 73 8 -3 90 11 0 12 1 13 -2 14 0 20 0 Sample Output 24.285 20.000