#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5 + 5;
const long long SQRTN = 1003;
const long long LOGN = 22;
const double PI = acos(-1.0);
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const long long FMOD = 998244353;
const double eps = 1e-9;
void __print(long long x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
T gcd(T a, T b) {
  if (b == 0) return a;
  a %= b;
  return gcd(b, a);
}
template <typename T>
T lcm(T a, T b) {
  return (a * (b / gcd(a, b)));
}
long long add(long long a, long long b, long long c = MOD) {
  long long res = a + b;
  return (res >= c ? res % c : res);
}
long long sub(long long a, long long b, long long c = MOD) {
  long long res;
  if (abs(a - b) < c)
    res = a - b;
  else
    res = (a - b) % c;
  return (res < 0 ? res + c : res);
}
long long mul(long long a, long long b, long long c = MOD) {
  long long res = (long long)a * b;
  return (res >= c ? res % c : res);
}
long long muln(long long a, long long b, long long c = MOD) {
  long long res = (long long)a * b;
  return ((res % c) + c) % c;
}
long long mulmod(long long a, long long b, long long m = MOD) {
  long long q = (long long)(((long double)a * (long double)b) / (long double)m);
  long long r = a * b - q * m;
  if (r > m) r %= m;
  if (r < 0) r += m;
  return r;
}
template <typename T>
T binpow(T e, T n) {
  T x = 1, p = e;
  while (n) {
    if (n & 1) x = x * p;
    p = p * p;
    n >>= 1;
  }
  return x;
}
template <typename T>
T binpow2(T e, T n, T m = MOD) {
  T x = 1, p = e;
  while (n) {
    if (n & 1) x = mul(x, p, m);
    p = mul(p, p, m);
    n >>= 1;
  }
  return x;
}
template <typename T>
T extended_euclid(T a, T b, T &x, T &y) {
  T xx = 0, yy = 1;
  y = 0;
  x = 1;
  while (b) {
    T q = a / b, t = b;
    b = a % b;
    a = t;
    t = xx;
    xx = x - q * xx;
    x = t;
    t = yy;
    yy = y - q * yy;
    y = t;
  }
  return a;
}
template <typename T>
T mod_inverse(T a, T n = MOD) {
  T x, y, z = 0;
  T d = extended_euclid(a, n, x, y);
  return (d > 1 ? -1 : sub(x, z, n));
}
const long long FACSZ = 1e4;
long long fact[FACSZ], ifact[FACSZ];
void precom(long long c = MOD) {
  fact[0] = 1;
  for (long long i = 1; i < FACSZ; i++) fact[i] = mul(fact[i - 1], i, c);
  ifact[FACSZ - 1] = mod_inverse(fact[FACSZ - 1], c);
  for (long long i = FACSZ - 1 - 1; i >= 0; i--) {
    ifact[i] = mul(i + 1, ifact[i + 1], c);
  }
}
vector<long long> primes;
void prime_precom() {
  primes.push_back(2);
  for (long long x = 3; primes.size() <= MAXN; x += 2) {
    bool isPrime = true;
    for (auto p : primes) {
      if (x % p == 0) {
        isPrime = false;
        break;
      }
      if (p * p > x) {
        break;
      }
    }
    if (isPrime) {
      primes.push_back(x);
    }
  }
}
long long ncr(long long n, long long k) {
  if (n < k) return 0;
  if (k == 0) return 1;
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 0; i < k; ++i) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
long long ncr_modp(long long n, long long k, long long c = MOD) {
  if (n < k) return 0;
  if (k == 0) return 1;
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 0; i < k; ++i) {
    res = mul(res, n - i, c);
    res = mul(res, binpow2(i + 1, c - 2, c), c);
  }
  return res;
}
vector<long long> factors;
void factorize(long long a) {
  factors.clear();
  for (long long i = 1; i * i <= a; i++) {
    if (a % i == 0) {
      factors.push_back(i);
      factors.push_back(a / i);
    }
  }
  sort(factors.begin(), factors.end());
}
long long ncr_precom(long long n, long long r, long long c = MOD) {
  return mul(mul(ifact[r], ifact[n - r], c), fact[n], c);
}
long long ceil(long long a, long long b) { return (a + b - 1) / b; }
bool is_prime(long long n) {
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return 0;
    }
  }
  return 1;
}
bool diophantine_checker(long long a, long long b, long long n) {
  for (long long i = 0; i * a <= n; i++) {
    if ((n - (i * a)) % b == 0) {
      return true;
    }
  }
  return false;
}
long long count_divisors(long long n) {
  long long c;
  long long ans = 1;
  for (long long i = 2; i * i <= n; i++) {
    c = 0;
    while (n % i == 0) {
      c++;
      n /= i;
    }
    ans *= (c + 1);
  }
  if (n > 2) {
    return ans * 2;
  }
  return ans;
}
string to_binary(long long n) {
  string r;
  while (n != 0) {
    r = (n % 2 == 0 ? "0" : "1") + r;
    n /= 2;
  }
  return r;
}
bool ispower2(long long x) { return x && (!(x & (x - 1))); }
vector<long long> spf;
void sieve() {
  spf.resize(MAXN);
  spf[1] = 1;
  for (long long i = 2; i < MAXN; i++) {
    spf[i] = i;
  }
  for (long long i = 4; i < MAXN; i += 2) {
    spf[i] = 2;
  }
  for (long long i = 3; i * i <= MAXN; i++) {
    if (spf[i] == i) {
      for (long long j = i * i; j < MAXN; j += i) {
        if (spf[j] == j) {
          spf[j] = i;
        }
      }
    }
  }
}
void pfactor(long long x, vector<long long> &ret) {
  while (x != 1) {
    ret.push_back(spf[x]);
    x = x / spf[x];
  }
}
struct point {
  long long x, y;
  void read() { cin >> x >> y; }
  point operator-=(const point &b) { return {x -= b.x, y -= b.y}; }
  long long operator*(const point &b) { return x * b.y - y * b.x; }
  point operator-(const point &b) { return {x - b.x, y - b.y}; }
};
long long n, k;
long double dist[MAXN], angle[MAXN];
bool check(long double r) {
  vector<pair<long double, long long>> val;
  long long cnt = 0;
  for (long long i = 0; i < n; i++) {
    if (dist[i] + eps >= 2 * r) {
      continue;
    }
    long double bd = acos(dist[i] / (2. * r));
    long double mn = angle[i] - bd, mx = angle[i] + bd;
    while (mn < -PI) {
      mn += 2 * PI;
    }
    while (mx < -PI) {
      mx += 2 * PI;
    }
    while (mn > PI) {
      mn -= 2 * PI;
    }
    while (mx > PI) {
      mx -= 2 * PI;
    }
    val.push_back(make_pair(mn, 1));
    val.push_back(make_pair(mx, -1));
    if (mn > mx) {
      cnt += 1;
    }
  }
  long long ans = cnt;
  sort(val.begin(), val.end());
  for (auto x : val) {
    cnt += x.second, ans = max(ans, cnt);
  }
  return ans >= k;
}
void solvethetestcase() {
  cin >> n >> k;
  vector<point> vv;
  for (long long i = 0; i < n; i++) {
    long long xx, yy;
    cin >> xx >> yy;
    if (xx == 0 && yy == 0) {
      --k, --n, --i;
    } else {
      vv.push_back(point{xx, yy});
    }
  }
  if (k <= 0) {
    cout << 0.0 << "\n";
    return;
  }
  for (long long i = 0; i < n; i++) {
    angle[i] = atan2(vv[i].y, vv[i].x);
    dist[i] = sqrtl(1. * vv[i].x * vv[i].x + 1. * vv[i].y * vv[i].y);
  }
  long double l = 0, r = 2e5;
  for (long long i = 0; i < 50; i++) {
    long double md = (l + r) * 0.5;
    if (check(md)) {
      r = md;
    } else {
      l = md;
    }
  }
  cout << r << "\n";
}
signed main() {
  cout << fixed << setprecision(12);
  ;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  for (long long testcase = 1; testcase < t + 1; testcase++) {
    solvethetestcase();
  }
}

### Prompt

Please create a solution in Cpp to the following problem:

Mr. Chanek lives in a city represented as a plane. He wants to build an amusement park in the shape of a circle of radius r. The circle must touch the origin (point (0, 0)).

There are n bird habitats that can be a photo spot for the tourists in the park. The i-th bird habitat is at point p_i = (x_i, y_i). 

Find the minimum radius r of a park with at least k bird habitats inside. 

A point is considered to be inside the park if and only if the distance between p_i and the center of the park is less than or equal to the radius of the park. Note that the center and the radius of the park do not need to be integers.

In this problem, it is guaranteed that the given input always has a solution with r ≤ 2 ⋅ 10^5.

Input

The first line contains two integers n and k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ n) — the number of bird habitats in the city and the number of bird habitats required to be inside the park.

The i-th of the next n lines contains two integers x_i and y_i (0 ≤ |x_i|, |y_i| ≤ 10^5) — the position of the i-th bird habitat.

Output

Output a single real number r denoting the minimum radius of a park with at least k bird habitats inside. It is guaranteed that the given input always has a solution with r ≤ 2 ⋅ 10^5.

Your answer is considered correct if its absolute or relative error does not exceed 10^{-4}.

Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-4}.

Examples

Input


8 4
-3 1
-4 4
1 5
2 2
2 -2
-2 -4
-1 -1
-6 0


Output


3.1622776589


Input


1 1
0 0


Output


0.0000000000

Note

In the first example, Mr. Chanek can put the center of the park at (-3, -1) with radius √{10} ≈ 3.162. It can be proven this is the minimum r.

The following illustrates the first example. The blue points represent bird habitats and the red circle represents the amusement park.

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5 + 5;
const long long SQRTN = 1003;
const long long LOGN = 22;
const double PI = acos(-1.0);
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const long long FMOD = 998244353;
const double eps = 1e-9;
void __print(long long x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
T gcd(T a, T b) {
  if (b == 0) return a;
  a %= b;
  return gcd(b, a);
}
template <typename T>
T lcm(T a, T b) {
  return (a * (b / gcd(a, b)));
}
long long add(long long a, long long b, long long c = MOD) {
  long long res = a + b;
  return (res >= c ? res % c : res);
}
long long sub(long long a, long long b, long long c = MOD) {
  long long res;
  if (abs(a - b) < c)
    res = a - b;
  else
    res = (a - b) % c;
  return (res < 0 ? res + c : res);
}
long long mul(long long a, long long b, long long c = MOD) {
  long long res = (long long)a * b;
  return (res >= c ? res % c : res);
}
long long muln(long long a, long long b, long long c = MOD) {
  long long res = (long long)a * b;
  return ((res % c) + c) % c;
}
long long mulmod(long long a, long long b, long long m = MOD) {
  long long q = (long long)(((long double)a * (long double)b) / (long double)m);
  long long r = a * b - q * m;
  if (r > m) r %= m;
  if (r < 0) r += m;
  return r;
}
template <typename T>
T binpow(T e, T n) {
  T x = 1, p = e;
  while (n) {
    if (n & 1) x = x * p;
    p = p * p;
    n >>= 1;
  }
  return x;
}
template <typename T>
T binpow2(T e, T n, T m = MOD) {
  T x = 1, p = e;
  while (n) {
    if (n & 1) x = mul(x, p, m);
    p = mul(p, p, m);
    n >>= 1;
  }
  return x;
}
template <typename T>
T extended_euclid(T a, T b, T &x, T &y) {
  T xx = 0, yy = 1;
  y = 0;
  x = 1;
  while (b) {
    T q = a / b, t = b;
    b = a % b;
    a = t;
    t = xx;
    xx = x - q * xx;
    x = t;
    t = yy;
    yy = y - q * yy;
    y = t;
  }
  return a;
}
template <typename T>
T mod_inverse(T a, T n = MOD) {
  T x, y, z = 0;
  T d = extended_euclid(a, n, x, y);
  return (d > 1 ? -1 : sub(x, z, n));
}
const long long FACSZ = 1e4;
long long fact[FACSZ], ifact[FACSZ];
void precom(long long c = MOD) {
  fact[0] = 1;
  for (long long i = 1; i < FACSZ; i++) fact[i] = mul(fact[i - 1], i, c);
  ifact[FACSZ - 1] = mod_inverse(fact[FACSZ - 1], c);
  for (long long i = FACSZ - 1 - 1; i >= 0; i--) {
    ifact[i] = mul(i + 1, ifact[i + 1], c);
  }
}
vector<long long> primes;
void prime_precom() {
  primes.push_back(2);
  for (long long x = 3; primes.size() <= MAXN; x += 2) {
    bool isPrime = true;
    for (auto p : primes) {
      if (x % p == 0) {
        isPrime = false;
        break;
      }
      if (p * p > x) {
        break;
      }
    }
    if (isPrime) {
      primes.push_back(x);
    }
  }
}
long long ncr(long long n, long long k) {
  if (n < k) return 0;
  if (k == 0) return 1;
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 0; i < k; ++i) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
long long ncr_modp(long long n, long long k, long long c = MOD) {
  if (n < k) return 0;
  if (k == 0) return 1;
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 0; i < k; ++i) {
    res = mul(res, n - i, c);
    res = mul(res, binpow2(i + 1, c - 2, c), c);
  }
  return res;
}
vector<long long> factors;
void factorize(long long a) {
  factors.clear();
  for (long long i = 1; i * i <= a; i++) {
    if (a % i == 0) {
      factors.push_back(i);
      factors.push_back(a / i);
    }
  }
  sort(factors.begin(), factors.end());
}
long long ncr_precom(long long n, long long r, long long c = MOD) {
  return mul(mul(ifact[r], ifact[n - r], c), fact[n], c);
}
long long ceil(long long a, long long b) { return (a + b - 1) / b; }
bool is_prime(long long n) {
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return 0;
    }
  }
  return 1;
}
bool diophantine_checker(long long a, long long b, long long n) {
  for (long long i = 0; i * a <= n; i++) {
    if ((n - (i * a)) % b == 0) {
      return true;
    }
  }
  return false;
}
long long count_divisors(long long n) {
  long long c;
  long long ans = 1;
  for (long long i = 2; i * i <= n; i++) {
    c = 0;
    while (n % i == 0) {
      c++;
      n /= i;
    }
    ans *= (c + 1);
  }
  if (n > 2) {
    return ans * 2;
  }
  return ans;
}
string to_binary(long long n) {
  string r;
  while (n != 0) {
    r = (n % 2 == 0 ? "0" : "1") + r;
    n /= 2;
  }
  return r;
}
bool ispower2(long long x) { return x && (!(x & (x - 1))); }
vector<long long> spf;
void sieve() {
  spf.resize(MAXN);
  spf[1] = 1;
  for (long long i = 2; i < MAXN; i++) {
    spf[i] = i;
  }
  for (long long i = 4; i < MAXN; i += 2) {
    spf[i] = 2;
  }
  for (long long i = 3; i * i <= MAXN; i++) {
    if (spf[i] == i) {
      for (long long j = i * i; j < MAXN; j += i) {
        if (spf[j] == j) {
          spf[j] = i;
        }
      }
    }
  }
}
void pfactor(long long x, vector<long long> &ret) {
  while (x != 1) {
    ret.push_back(spf[x]);
    x = x / spf[x];
  }
}
struct point {
  long long x, y;
  void read() { cin >> x >> y; }
  point operator-=(const point &b) { return {x -= b.x, y -= b.y}; }
  long long operator*(const point &b) { return x * b.y - y * b.x; }
  point operator-(const point &b) { return {x - b.x, y - b.y}; }
};
long long n, k;
long double dist[MAXN], angle[MAXN];
bool check(long double r) {
  vector<pair<long double, long long>> val;
  long long cnt = 0;
  for (long long i = 0; i < n; i++) {
    if (dist[i] + eps >= 2 * r) {
      continue;
    }
    long double bd = acos(dist[i] / (2. * r));
    long double mn = angle[i] - bd, mx = angle[i] + bd;
    while (mn < -PI) {
      mn += 2 * PI;
    }
    while (mx < -PI) {
      mx += 2 * PI;
    }
    while (mn > PI) {
      mn -= 2 * PI;
    }
    while (mx > PI) {
      mx -= 2 * PI;
    }
    val.push_back(make_pair(mn, 1));
    val.push_back(make_pair(mx, -1));
    if (mn > mx) {
      cnt += 1;
    }
  }
  long long ans = cnt;
  sort(val.begin(), val.end());
  for (auto x : val) {
    cnt += x.second, ans = max(ans, cnt);
  }
  return ans >= k;
}
void solvethetestcase() {
  cin >> n >> k;
  vector<point> vv;
  for (long long i = 0; i < n; i++) {
    long long xx, yy;
    cin >> xx >> yy;
    if (xx == 0 && yy == 0) {
      --k, --n, --i;
    } else {
      vv.push_back(point{xx, yy});
    }
  }
  if (k <= 0) {
    cout << 0.0 << "\n";
    return;
  }
  for (long long i = 0; i < n; i++) {
    angle[i] = atan2(vv[i].y, vv[i].x);
    dist[i] = sqrtl(1. * vv[i].x * vv[i].x + 1. * vv[i].y * vv[i].y);
  }
  long double l = 0, r = 2e5;
  for (long long i = 0; i < 50; i++) {
    long double md = (l + r) * 0.5;
    if (check(md)) {
      r = md;
    } else {
      l = md;
    }
  }
  cout << r << "\n";
}
signed main() {
  cout << fixed << setprecision(12);
  ;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  for (long long testcase = 1; testcase < t + 1; testcase++) {
    solvethetestcase();
  }
}

```