#include <bits/stdc++.h>
using namespace std;
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << "\n";
  err(++it, args...);
}
const double PI = acos(-1);
const double eps = (1e-9);
const long long int INF = 2e18;
const int N = (1e6) + 3;
int cnt[N], vis[N];
void solve() {
  int n, i, j, k, a;
  scanf("%d%d", &n, &k);
  vector<int> v(n);
  for (i = 0; i < n; i++) scanf("%d", &v[i]);
  sort(v.begin(), v.end());
  for (i = 0; i < n; ++i) {
    for (j = i + 1; j < n; ++j) a = v[j] - v[i], cnt[a]++;
  }
  int c, m = ((long long int)(k) * (long long int)(k + 1)) / 2;
  for (i = 1; i < N; ++i) {
    a = 0, j = i;
    while (a <= m && j < N) a += cnt[j], j += i;
    if (a <= m) {
      a = 0;
      for (j = 0; j < n; ++j) {
        c = (v[j] % i);
        if (vis[c]) a++;
        vis[c] = 1;
      }
      if (a <= k) printf("%d\n", i), exit(0);
      for (j = 0; j < i; ++j) vis[j] = 0;
    }
  }
}
int main() {
  int t = 1;
  while (t--) solve();
}

### Prompt

Please create a solution in cpp to 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;
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << "\n";
  err(++it, args...);
}
const double PI = acos(-1);
const double eps = (1e-9);
const long long int INF = 2e18;
const int N = (1e6) + 3;
int cnt[N], vis[N];
void solve() {
  int n, i, j, k, a;
  scanf("%d%d", &n, &k);
  vector<int> v(n);
  for (i = 0; i < n; i++) scanf("%d", &v[i]);
  sort(v.begin(), v.end());
  for (i = 0; i < n; ++i) {
    for (j = i + 1; j < n; ++j) a = v[j] - v[i], cnt[a]++;
  }
  int c, m = ((long long int)(k) * (long long int)(k + 1)) / 2;
  for (i = 1; i < N; ++i) {
    a = 0, j = i;
    while (a <= m && j < N) a += cnt[j], j += i;
    if (a <= m) {
      a = 0;
      for (j = 0; j < n; ++j) {
        c = (v[j] % i);
        if (vis[c]) a++;
        vis[c] = 1;
      }
      if (a <= k) printf("%d\n", i), exit(0);
      for (j = 0; j < i; ++j) vis[j] = 0;
    }
  }
}
int main() {
  int t = 1;
  while (t--) solve();
}

```