#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void OUTLN(T &arr, int len) {
  for (int i = 0; i < len; i++) cout << arr[i] << " ";
  cout << endl;
}
const double eps = 1e-9;
const double pi = acos(-1.0);
const int oo = 1000000000;
const int mod = 1000000007;
const double E = 2.7182818284590452353602874713527;
int n, k, _max;
int arr[5000 + 5];
bool vis[1000000 + 5];
int vt[1000000 + 5][10];
int vtn[1000000 + 5];
int vr[1000000 + 5];
int vrn;
bool taken[1000000 + 5];
int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
  if (n - k <= 1) {
    printf("1\n");
    return 0;
  }
  sort(arr, arr + n);
  _max = arr[n - 1] - arr[0] + 1;
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
      int cur_m = arr[j] - arr[i];
      if (vtn[cur_m] < k * 2 + 1) {
        vt[cur_m][vtn[cur_m]++] = arr[i];
        vt[cur_m][vtn[cur_m]++] = arr[j];
      }
    }
  int rec;
  for (int i = 1; i <= _max; i++) {
    rec = 0;
    vrn = 0;
    for (int cur = i; cur <= _max; cur += i) {
      if (rec > k) break;
      for (int t = 0; t < vtn[cur]; t++) {
        if (taken[vt[cur][t]]) continue;
        taken[vt[cur][t]] = true;
        vr[vrn++] = vt[cur][t];
        int cur_m = vt[cur][t] % i;
        if (vis[cur_m]) {
          rec++;
          if (rec > k) break;
        } else {
          vis[cur_m] = true;
        }
      }
    }
    if (rec <= k) {
      printf("%d\n", i);
      break;
    }
    for (int j = 0; j < vrn; j++) {
      vis[vr[j] % i] = false;
      taken[vr[j]] = false;
    }
  }
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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 <class T>
inline void OUTLN(T &arr, int len) {
  for (int i = 0; i < len; i++) cout << arr[i] << " ";
  cout << endl;
}
const double eps = 1e-9;
const double pi = acos(-1.0);
const int oo = 1000000000;
const int mod = 1000000007;
const double E = 2.7182818284590452353602874713527;
int n, k, _max;
int arr[5000 + 5];
bool vis[1000000 + 5];
int vt[1000000 + 5][10];
int vtn[1000000 + 5];
int vr[1000000 + 5];
int vrn;
bool taken[1000000 + 5];
int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
  if (n - k <= 1) {
    printf("1\n");
    return 0;
  }
  sort(arr, arr + n);
  _max = arr[n - 1] - arr[0] + 1;
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
      int cur_m = arr[j] - arr[i];
      if (vtn[cur_m] < k * 2 + 1) {
        vt[cur_m][vtn[cur_m]++] = arr[i];
        vt[cur_m][vtn[cur_m]++] = arr[j];
      }
    }
  int rec;
  for (int i = 1; i <= _max; i++) {
    rec = 0;
    vrn = 0;
    for (int cur = i; cur <= _max; cur += i) {
      if (rec > k) break;
      for (int t = 0; t < vtn[cur]; t++) {
        if (taken[vt[cur][t]]) continue;
        taken[vt[cur][t]] = true;
        vr[vrn++] = vt[cur][t];
        int cur_m = vt[cur][t] % i;
        if (vis[cur_m]) {
          rec++;
          if (rec > k) break;
        } else {
          vis[cur_m] = true;
        }
      }
    }
    if (rec <= k) {
      printf("%d\n", i);
      break;
    }
    for (int j = 0; j < vrn; j++) {
      vis[vr[j] % i] = false;
      taken[vr[j]] = false;
    }
  }
  return 0;
}

```