#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> p;
int n, k;
pair<int, int> start, ool;
int startIdx = -5;
float check_slope(pair<int, int>& a, pair<int, int>& b) {
  int xd = b.first - a.first;
  if (xd == 0) return std::numeric_limits<float>::infinity();
  int yd = b.second - a.second;
  return (float)yd / (float)xd;
}
float dist(pair<int, int>& a, pair<int, int>& b) {
  return sqrtf(powf((float)(a.first - b.first), 2) +
               powf((float)(a.second - b.second), 2));
}
float e_ival(int l, int r) {
  if (r < l) return 0;
  if (l <= startIdx && startIdx <= r) {
    float rl = dist(start, p[l]) + dist(p[l], p[r]) + dist(p[r], ool);
    float rr = dist(start, p[r]) + dist(p[r], p[l]) + dist(p[l], ool);
    return min(rl, rr);
  } else {
    return dist(p[l], p[r]) + min(dist(p[l], ool), dist(p[r], ool));
  }
}
int main() {
  cin >> n >> k;
  p.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i].first >> p[i].second;
  }
  start = p[k - 1];
  float slope;
  int slref;
  for (int i = 0; i < 4; i++) {
    slope = check_slope(p[i], p[(i + 1) % 4]);
    if (slope == check_slope(p[(i + 1) % 4], p[(i + 2) % 4])) {
      slref = i;
      break;
    }
  }
  bool sool = false;
  for (int i = 0; i < n; i++) {
    if (i == slref) continue;
    if (check_slope(p[slref], p[i]) != slope) {
      ool = p[i];
      sool = i == k - 1;
      swap(p[i], p.back());
      p.pop_back();
      break;
    }
  }
  sort(p.begin(), p.end());
  if (sool) {
    cout << setprecision(10) << e_ival(0, n - 2) << endl;
    return 0;
  }
  startIdx = (int)distance(p.begin(), lower_bound(p.begin(), p.end(), start));
  float res = std::numeric_limits<float>::infinity();
  for (int i = -1; i <= n - 2; i++) {
    float v = e_ival(0, i) + e_ival(i + 1, n - 2);
    res = min(res, v);
  }
  cout << setprecision(10) << res << endl;
}

### Prompt

In Cpp, your task is to solve 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;
vector<pair<int, int>> p;
int n, k;
pair<int, int> start, ool;
int startIdx = -5;
float check_slope(pair<int, int>& a, pair<int, int>& b) {
  int xd = b.first - a.first;
  if (xd == 0) return std::numeric_limits<float>::infinity();
  int yd = b.second - a.second;
  return (float)yd / (float)xd;
}
float dist(pair<int, int>& a, pair<int, int>& b) {
  return sqrtf(powf((float)(a.first - b.first), 2) +
               powf((float)(a.second - b.second), 2));
}
float e_ival(int l, int r) {
  if (r < l) return 0;
  if (l <= startIdx && startIdx <= r) {
    float rl = dist(start, p[l]) + dist(p[l], p[r]) + dist(p[r], ool);
    float rr = dist(start, p[r]) + dist(p[r], p[l]) + dist(p[l], ool);
    return min(rl, rr);
  } else {
    return dist(p[l], p[r]) + min(dist(p[l], ool), dist(p[r], ool));
  }
}
int main() {
  cin >> n >> k;
  p.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i].first >> p[i].second;
  }
  start = p[k - 1];
  float slope;
  int slref;
  for (int i = 0; i < 4; i++) {
    slope = check_slope(p[i], p[(i + 1) % 4]);
    if (slope == check_slope(p[(i + 1) % 4], p[(i + 2) % 4])) {
      slref = i;
      break;
    }
  }
  bool sool = false;
  for (int i = 0; i < n; i++) {
    if (i == slref) continue;
    if (check_slope(p[slref], p[i]) != slope) {
      ool = p[i];
      sool = i == k - 1;
      swap(p[i], p.back());
      p.pop_back();
      break;
    }
  }
  sort(p.begin(), p.end());
  if (sool) {
    cout << setprecision(10) << e_ival(0, n - 2) << endl;
    return 0;
  }
  startIdx = (int)distance(p.begin(), lower_bound(p.begin(), p.end(), start));
  float res = std::numeric_limits<float>::infinity();
  for (int i = -1; i <= n - 2; i++) {
    float v = e_ival(0, i) + e_ival(i + 1, n - 2);
    res = min(res, v);
  }
  cout << setprecision(10) << res << endl;
}

```