#include <bits/stdc++.h>
using namespace std;
template <typename T>
string to_s(const T& v);
template <>
string to_s(const string& v);
template <>
string to_s(const bool& v);
template <typename T>
string to_s(const vector<T>& v);
template <typename T>
string to_s(const list<T>& v);
template <typename T>
string to_s(const set<T>& v);
template <typename F, typename S>
string to_s(const pair<F, S>& v);
template <typename K, typename V>
string to_s(const map<K, V>& v);
int main(int argc, char* argv[]) {
  int n, k;
  cin >> n >> k;
  vector<int> a;
  for (int nn = static_cast<int>(0); nn < static_cast<int>(n); ++nn) {
    int aa;
    cin >> aa;
    a.push_back(aa);
  }
  if (n - k <= 1) {
    cout << 1 << endl;
    return 0;
  }
  vector<int> d(1000002, 0);
  for (int k = static_cast<int>(0); k < static_cast<int>(n); ++k) {
    for (int j = static_cast<int>(k + 1); j < static_cast<int>(n); ++j) {
      int dd = abs(a[k] - a[j]);
      ++d[dd];
    }
  }
  long long m = n - k - 1;
  while (true) {
    ++m;
    int p = 0;
    for (int x = static_cast<int>(m); m > 0 ? x <= static_cast<int>(1000001)
                                            : x >= static_cast<int>(1000001);
         x += static_cast<int>(m)) {
      p += d[x];
    }
    if (p > k * (k + 1) / 2) continue;
    vector<int> s(n);
    for (int nn = static_cast<int>(0); nn < static_cast<int>(n); ++nn) {
      int mod = a[nn] % m;
      s[nn] = mod;
    }
    sort(s.begin(), s.end());
    int over = 0;
    for (int nn = static_cast<int>(1); nn <= static_cast<int>(n - 1); ++nn) {
      if (s[nn] == s[nn - 1]) over += 1;
    }
    if (over <= k) {
      cout << m << endl;
      break;
    }
  }
  return 0;
}
template <typename T>
string to_s(const T& v) {
  ostringstream oss;
  oss << v;
  return oss.str();
}
template <>
string to_s(const string& v) {
  ostringstream oss;
  oss << '"' << v << '"';
  return oss.str();
}
template <>
string to_s(const bool& v) {
  ostringstream oss;
  oss << (v ? "true" : "false");
  return oss.str();
}
template <typename T>
string to_s(const vector<T>& v) {
  ostringstream oss;
  oss << "[";
  for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
    oss << to_s(*i) << ",";
  oss << "]";
  return oss.str();
}
template <typename T>
string to_s(const list<T>& v) {
  ostringstream oss;
  oss << "(";
  for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
    oss << to_s(*i) << ",";
  oss << ")";
  return oss.str();
}
template <typename T>
string to_s(const set<T>& v) {
  ostringstream oss;
  oss << "{";
  for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
    oss << to_s(*i) << ",";
  oss << "}";
  return oss.str();
}
template <typename F, typename S>
string to_s(const pair<F, S>& v) {
  ostringstream oss;
  oss << "<" << to_s(v.first) << " " << to_s(v.second) << ">";
  return oss.str();
}
template <typename K, typename V>
string to_s(const map<K, V>& v) {
  ostringstream oss;
  oss << "{";
  for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
    oss << to_s(i->first) << " => " << to_s(i->second) << ",";
  oss << "}";
  return oss.str();
}

### Prompt

In Cpp, your task is to solve the following problem:

You have been given n distinct integers a1, a2, ..., an. You can remove at most k of them. Find the minimum modular m (m > 0), so that for every pair of the remaining integers (ai, aj), the following unequality holds: <image>.

Input

The first line contains two integers n and k (1 ≤ n ≤ 5000, 0 ≤ k ≤ 4), which we have mentioned above. 

The second line contains n distinct integers a1, a2, ..., an (0 ≤ ai ≤ 106).

Output

Print a single positive integer — the minimum m.

Examples

Input

7 0
0 2 3 6 7 12 18


Output

13


Input

7 1
0 2 3 6 7 12 18


Output

7

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
string to_s(const T& v);
template <>
string to_s(const string& v);
template <>
string to_s(const bool& v);
template <typename T>
string to_s(const vector<T>& v);
template <typename T>
string to_s(const list<T>& v);
template <typename T>
string to_s(const set<T>& v);
template <typename F, typename S>
string to_s(const pair<F, S>& v);
template <typename K, typename V>
string to_s(const map<K, V>& v);
int main(int argc, char* argv[]) {
  int n, k;
  cin >> n >> k;
  vector<int> a;
  for (int nn = static_cast<int>(0); nn < static_cast<int>(n); ++nn) {
    int aa;
    cin >> aa;
    a.push_back(aa);
  }
  if (n - k <= 1) {
    cout << 1 << endl;
    return 0;
  }
  vector<int> d(1000002, 0);
  for (int k = static_cast<int>(0); k < static_cast<int>(n); ++k) {
    for (int j = static_cast<int>(k + 1); j < static_cast<int>(n); ++j) {
      int dd = abs(a[k] - a[j]);
      ++d[dd];
    }
  }
  long long m = n - k - 1;
  while (true) {
    ++m;
    int p = 0;
    for (int x = static_cast<int>(m); m > 0 ? x <= static_cast<int>(1000001)
                                            : x >= static_cast<int>(1000001);
         x += static_cast<int>(m)) {
      p += d[x];
    }
    if (p > k * (k + 1) / 2) continue;
    vector<int> s(n);
    for (int nn = static_cast<int>(0); nn < static_cast<int>(n); ++nn) {
      int mod = a[nn] % m;
      s[nn] = mod;
    }
    sort(s.begin(), s.end());
    int over = 0;
    for (int nn = static_cast<int>(1); nn <= static_cast<int>(n - 1); ++nn) {
      if (s[nn] == s[nn - 1]) over += 1;
    }
    if (over <= k) {
      cout << m << endl;
      break;
    }
  }
  return 0;
}
template <typename T>
string to_s(const T& v) {
  ostringstream oss;
  oss << v;
  return oss.str();
}
template <>
string to_s(const string& v) {
  ostringstream oss;
  oss << '"' << v << '"';
  return oss.str();
}
template <>
string to_s(const bool& v) {
  ostringstream oss;
  oss << (v ? "true" : "false");
  return oss.str();
}
template <typename T>
string to_s(const vector<T>& v) {
  ostringstream oss;
  oss << "[";
  for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
    oss << to_s(*i) << ",";
  oss << "]";
  return oss.str();
}
template <typename T>
string to_s(const list<T>& v) {
  ostringstream oss;
  oss << "(";
  for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
    oss << to_s(*i) << ",";
  oss << ")";
  return oss.str();
}
template <typename T>
string to_s(const set<T>& v) {
  ostringstream oss;
  oss << "{";
  for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
    oss << to_s(*i) << ",";
  oss << "}";
  return oss.str();
}
template <typename F, typename S>
string to_s(const pair<F, S>& v) {
  ostringstream oss;
  oss << "<" << to_s(v.first) << " " << to_s(v.second) << ">";
  return oss.str();
}
template <typename K, typename V>
string to_s(const map<K, V>& v) {
  ostringstream oss;
  oss << "{";
  for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
    oss << to_s(i->first) << " => " << to_s(i->second) << ",";
  oss << "}";
  return oss.str();
}

```