#include <bits/stdc++.h>
#pragma comment(linker, "/stack:256000000")
using namespace std;
const int N = 1000100;
vector<pair<int, int> > v[N];
int a[5010];
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int(i) = 0; (i) < (n); (i)++) scanf("%d", &a[i]);
  for (int(i) = 0; (i) < (n); (i)++)
    for (int(j) = 0; (j) < (i); (j)++) {
      int d = abs(a[i] - a[j]);
      if ((int)(v[d]).size() > k)
        continue;
      else
        v[d].push_back(make_pair(min(a[i], a[j]), max(a[i], a[j])));
    }
  for (int ans = 1; ans < N; ans++) {
    int x = ans;
    bool OK = 1;
    vector<pair<int, int> > ids;
    while (x < N) {
      if ((int)(v[x]).size() > k) {
        OK = 0;
        break;
      }
      ids.push_back(make_pair((int)(v[x]).size(), x));
      x += ans;
    }
    if (!OK) continue;
    sort((ids).begin(), (ids).end(), greater<pair<int, int> >());
    set<int> used;
    if (k > 0) {
      for (int(i) = 0; (i) < ((int)(ids).size()); (i)++) {
        for (int(j) = 0; (j) < ((int)(v[ids[i].second]).size()); (j)++) {
          used.insert(v[ids[i].second][j].first);
          if ((int)(used).size() == k) break;
        }
        if ((int)(used).size() == k) break;
      }
    }
    for (int(i) = 0; (i) < ((int)(ids).size()); (i)++) {
      for (int(j) = 0; (j) < ((int)(v[ids[i].second]).size()); (j)++) {
        pair<int, int> x = v[ids[i].second][j];
        if (!used.count(x.first) && !used.count(x.second)) {
          OK = 0;
          break;
        }
      }
      if (!OK) break;
    }
    if (OK) {
      cout << ans << endl;
      break;
    }
  }
  return 0;
}

### Prompt

Create a solution in cpp for 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>
#pragma comment(linker, "/stack:256000000")
using namespace std;
const int N = 1000100;
vector<pair<int, int> > v[N];
int a[5010];
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int(i) = 0; (i) < (n); (i)++) scanf("%d", &a[i]);
  for (int(i) = 0; (i) < (n); (i)++)
    for (int(j) = 0; (j) < (i); (j)++) {
      int d = abs(a[i] - a[j]);
      if ((int)(v[d]).size() > k)
        continue;
      else
        v[d].push_back(make_pair(min(a[i], a[j]), max(a[i], a[j])));
    }
  for (int ans = 1; ans < N; ans++) {
    int x = ans;
    bool OK = 1;
    vector<pair<int, int> > ids;
    while (x < N) {
      if ((int)(v[x]).size() > k) {
        OK = 0;
        break;
      }
      ids.push_back(make_pair((int)(v[x]).size(), x));
      x += ans;
    }
    if (!OK) continue;
    sort((ids).begin(), (ids).end(), greater<pair<int, int> >());
    set<int> used;
    if (k > 0) {
      for (int(i) = 0; (i) < ((int)(ids).size()); (i)++) {
        for (int(j) = 0; (j) < ((int)(v[ids[i].second]).size()); (j)++) {
          used.insert(v[ids[i].second][j].first);
          if ((int)(used).size() == k) break;
        }
        if ((int)(used).size() == k) break;
      }
    }
    for (int(i) = 0; (i) < ((int)(ids).size()); (i)++) {
      for (int(j) = 0; (j) < ((int)(v[ids[i].second]).size()); (j)++) {
        pair<int, int> x = v[ids[i].second][j];
        if (!used.count(x.first) && !used.count(x.second)) {
          OK = 0;
          break;
        }
      }
      if (!OK) break;
    }
    if (OK) {
      cout << ans << endl;
      break;
    }
  }
  return 0;
}

```