#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T &t) {
  t = 0;
  char ch = getchar();
  int f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  do {
    (t *= 10) += ch - '0';
    ch = getchar();
  } while ('0' <= ch && ch <= '9');
  t *= f;
}
template <typename T>
void write(T t) {
  if (t < 0) {
    putchar('-');
    write(-t);
    return;
  }
  if (t > 9) write(t / 10);
  putchar('0' + t % 10);
}
template <typename T>
void writeln(T t) {
  write(t);
  puts("");
}
const int maxn = (2e5) + 10;
const double eps = 1e-6;
int n, K;
double ans = 1e18;
struct node {
  int x, y, id;
} d[maxn];
long long sqr(long long x) { return x * x; }
double dis(node A, node B) {
  return sqrt(sqr(A.x - B.x) * 1.0 + sqr(A.y - B.y) * 1.0);
}
bool cmp(node A, node B) { return (A.x == B.x ? A.y < B.y : A.x < B.x); }
int tot, p[10];
double t[1000], rem[10][10];
double Get(node A, node B) {
  return (A.x == B.x ? 1e9 : (A.y - B.y) * 1.0 / (A.x - B.x));
}
int main() {
  read(n);
  read(K);
  for (int i = 1; i <= n; i++) read(d[i].x), read(d[i].y);
  if (n <= 3) {
    p[1] = K;
    tot = 1;
    for (int i = 1; i <= n; i++)
      if (i != K) p[++tot] = i;
    do {
      double tmp = 0;
      for (int i = 1; i < n; i++) tmp += dis(d[p[i]], d[p[i + 1]]);
      ans = min(ans, tmp);
    } while (next_permutation(p + 2, p + n + 1));
    printf("%.10lf\n", ans);
    return 0;
  }
  for (int i = 1; i <= n; i++) d[i].id = i;
  random_shuffle(d + 1, d + n + 1);
  for (int i = 1; i <= 4; i++)
    for (int j = i + 1; j <= 4; j++) {
      t[++tot] = rem[i][j] = Get(d[i], d[j]);
    }
  sort(t + 1, t + tot + 1);
  int L = 1, R = -1, pos, mx = 0;
  for (int i = 1; i <= tot + 1; i++) {
    if (i > tot || fabs(t[i] - t[i - 1]) > eps) {
      if (L != -1 && R != -1) {
        if (R - L + 1 > mx) mx = R - L + 1, pos = L;
      }
      L = R = i + 1;
    } else
      R = max(R, i);
  }
  int fd = -1;
  for (int i = 1; i <= 4 && fd == -1; i++)
    for (int j = i + 1; j <= 4 && fd == -1; j++) {
      if (fabs(rem[i][j] - t[pos]) < eps) {
        fd = i;
        break;
      }
    }
  for (int i = 2; i <= n; i++)
    if (fabs(Get(d[fd], d[i]) - t[pos]) > eps) {
      fd = i;
      break;
    }
  swap(d[fd], d[n]);
  sort(d + 1, d + n, cmp);
  for (int i = 1; i <= n; i++)
    if (d[i].id == K) {
      K = i;
      break;
    }
  if (K == n) {
    ans = dis(d[1], d[n - 1]) + min(dis(d[n], d[n - 1]), dis(d[n], d[1]));
  } else {
    for (int i = K; i < n; i++) {
      ans = min(
          ans,
          dis(d[K], d[i]) + dis(d[i], d[1]) + dis(d[1], d[n]) +
              (i != n - 1 ? dis(d[n], d[i + 1]) + dis(d[i + 1], d[n - 1]) : 0));
      ans = min(
          ans,
          dis(d[K], d[1]) + dis(d[1], d[i]) + dis(d[i], d[n]) +
              (i != n - 1 ? dis(d[n], d[i + 1]) + dis(d[i + 1], d[n - 1]) : 0));
    }
    reverse(d + 1, d + n);
    K = n - K;
    for (int i = K; i < n; i++) {
      ans = min(
          ans,
          dis(d[K], d[i]) + dis(d[i], d[1]) + dis(d[1], d[n]) +
              (i != n - 1 ? dis(d[n], d[i + 1]) + dis(d[i + 1], d[n - 1]) : 0));
      ans = min(
          ans,
          dis(d[K], d[1]) + dis(d[1], d[i]) + dis(d[i], d[n]) +
              (i != n - 1 ? dis(d[n], d[i + 1]) + dis(d[i + 1], d[n - 1]) : 0));
    }
  }
  printf("%.10lf\n", ans);
  return 0;
}

### Prompt

Generate a Cpp solution to the following problem:

You are given N points on an infinite plane with the Cartesian coordinate system on it. N-1 points lay on one line, and one point isn't on that line. You are on point K at the start, and the goal is to visit every point. You can move between any two points in a straight line, and you can revisit points. What is the minimum length of the path? 

Input

The first line contains two integers: N (3 ≤ N ≤ 2*10^5) - the number of points, and K (1 ≤ K ≤ N) - the index of the starting point.

Each of the next N lines contain two integers, A_i, B_i (-10^6 ≤ A_i, B_i ≤ 10^6) - coordinates of the i-th point.

Output

The output contains one number - the shortest path to visit all given points starting from point K. The absolute difference between your solution and the main solution shouldn't exceed 10^-6;

Example

Input


5 2
0 0
-1 1
2 -2
0 1
-2 2


Output


7.478709

Note

The shortest path consists of these moves: 

2 -> 5 

5 -> 4 

4 -> 1 

1 -> 3 

There isn't any shorter path possible.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T &t) {
  t = 0;
  char ch = getchar();
  int f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  do {
    (t *= 10) += ch - '0';
    ch = getchar();
  } while ('0' <= ch && ch <= '9');
  t *= f;
}
template <typename T>
void write(T t) {
  if (t < 0) {
    putchar('-');
    write(-t);
    return;
  }
  if (t > 9) write(t / 10);
  putchar('0' + t % 10);
}
template <typename T>
void writeln(T t) {
  write(t);
  puts("");
}
const int maxn = (2e5) + 10;
const double eps = 1e-6;
int n, K;
double ans = 1e18;
struct node {
  int x, y, id;
} d[maxn];
long long sqr(long long x) { return x * x; }
double dis(node A, node B) {
  return sqrt(sqr(A.x - B.x) * 1.0 + sqr(A.y - B.y) * 1.0);
}
bool cmp(node A, node B) { return (A.x == B.x ? A.y < B.y : A.x < B.x); }
int tot, p[10];
double t[1000], rem[10][10];
double Get(node A, node B) {
  return (A.x == B.x ? 1e9 : (A.y - B.y) * 1.0 / (A.x - B.x));
}
int main() {
  read(n);
  read(K);
  for (int i = 1; i <= n; i++) read(d[i].x), read(d[i].y);
  if (n <= 3) {
    p[1] = K;
    tot = 1;
    for (int i = 1; i <= n; i++)
      if (i != K) p[++tot] = i;
    do {
      double tmp = 0;
      for (int i = 1; i < n; i++) tmp += dis(d[p[i]], d[p[i + 1]]);
      ans = min(ans, tmp);
    } while (next_permutation(p + 2, p + n + 1));
    printf("%.10lf\n", ans);
    return 0;
  }
  for (int i = 1; i <= n; i++) d[i].id = i;
  random_shuffle(d + 1, d + n + 1);
  for (int i = 1; i <= 4; i++)
    for (int j = i + 1; j <= 4; j++) {
      t[++tot] = rem[i][j] = Get(d[i], d[j]);
    }
  sort(t + 1, t + tot + 1);
  int L = 1, R = -1, pos, mx = 0;
  for (int i = 1; i <= tot + 1; i++) {
    if (i > tot || fabs(t[i] - t[i - 1]) > eps) {
      if (L != -1 && R != -1) {
        if (R - L + 1 > mx) mx = R - L + 1, pos = L;
      }
      L = R = i + 1;
    } else
      R = max(R, i);
  }
  int fd = -1;
  for (int i = 1; i <= 4 && fd == -1; i++)
    for (int j = i + 1; j <= 4 && fd == -1; j++) {
      if (fabs(rem[i][j] - t[pos]) < eps) {
        fd = i;
        break;
      }
    }
  for (int i = 2; i <= n; i++)
    if (fabs(Get(d[fd], d[i]) - t[pos]) > eps) {
      fd = i;
      break;
    }
  swap(d[fd], d[n]);
  sort(d + 1, d + n, cmp);
  for (int i = 1; i <= n; i++)
    if (d[i].id == K) {
      K = i;
      break;
    }
  if (K == n) {
    ans = dis(d[1], d[n - 1]) + min(dis(d[n], d[n - 1]), dis(d[n], d[1]));
  } else {
    for (int i = K; i < n; i++) {
      ans = min(
          ans,
          dis(d[K], d[i]) + dis(d[i], d[1]) + dis(d[1], d[n]) +
              (i != n - 1 ? dis(d[n], d[i + 1]) + dis(d[i + 1], d[n - 1]) : 0));
      ans = min(
          ans,
          dis(d[K], d[1]) + dis(d[1], d[i]) + dis(d[i], d[n]) +
              (i != n - 1 ? dis(d[n], d[i + 1]) + dis(d[i + 1], d[n - 1]) : 0));
    }
    reverse(d + 1, d + n);
    K = n - K;
    for (int i = K; i < n; i++) {
      ans = min(
          ans,
          dis(d[K], d[i]) + dis(d[i], d[1]) + dis(d[1], d[n]) +
              (i != n - 1 ? dis(d[n], d[i + 1]) + dis(d[i + 1], d[n - 1]) : 0));
      ans = min(
          ans,
          dis(d[K], d[1]) + dis(d[1], d[i]) + dis(d[i], d[n]) +
              (i != n - 1 ? dis(d[n], d[i + 1]) + dis(d[i + 1], d[n - 1]) : 0));
    }
  }
  printf("%.10lf\n", ans);
  return 0;
}

```