#include <bits/stdc++.h>
using namespace std;
void bug() { cout << " " << endl; }
template <class T>
void bug(T a) {
  cout << a << "  ";
}
template <class T>
void bug(T* a, int n) {
  for (int i = 0; i < (n); i++) bug(a[i]);
}
const int maxn = 1111111;
int n, k;
int a[5555];
int cnt[1111111];
int b[1111111][13];
int main() {
  cin >> n >> k;
  for (int i = 0; i < (n); i++) cin >> a[i];
  for (int i = 0; i < (n); i++)
    for (int j = i + 1; j < n; j++) {
      int x = 0;
      if (a[i] > a[j])
        x = a[i] - a[j];
      else
        x = a[j] - a[i];
      if (cnt[x] > 10) continue;
      int ok_i = 1, ok_j = 1;
      for (int k = 0; k < (cnt[x]); k++)
        if (b[x][k] == i) ok_i = 0;
      for (int k = 0; k < (cnt[x]); k++)
        if (b[x][k] == j) ok_j = 0;
      if (ok_i) b[x][cnt[x]++] = i;
      if (ok_j) b[x][cnt[x]++] = j;
    }
  int arr[13], c, vis[13];
  for (int i = 0; i < (1111111); i++)
    if (i) {
      c = 0;
      for (int j = i; c < 10 && j < 1111111; j += i) {
        for (int k = 0; k < (cnt[j]); k++)
          if (c < 10) {
            int ok = 1;
            for (int l = 0; l < (c); l++)
              if (arr[l] == a[b[j][k]]) ok = 0;
            if (ok) arr[c++] = a[b[j][k]];
          }
      }
      int total = c;
      memset(vis, 0, sizeof(vis));
      for (int k = 0; k < (c); k++)
        if (!vis[k]) {
          total--;
          for (int j = 0; j < (c); j++)
            if (j > k && arr[j] % i == arr[k] % i) vis[j] = 1;
        }
      if (total <= k) {
        cout << i << endl;
        return 0;
      }
    }
  return 0;
}

### Prompt

Your challenge is to write a CPP solution 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 bug() { cout << " " << endl; }
template <class T>
void bug(T a) {
  cout << a << "  ";
}
template <class T>
void bug(T* a, int n) {
  for (int i = 0; i < (n); i++) bug(a[i]);
}
const int maxn = 1111111;
int n, k;
int a[5555];
int cnt[1111111];
int b[1111111][13];
int main() {
  cin >> n >> k;
  for (int i = 0; i < (n); i++) cin >> a[i];
  for (int i = 0; i < (n); i++)
    for (int j = i + 1; j < n; j++) {
      int x = 0;
      if (a[i] > a[j])
        x = a[i] - a[j];
      else
        x = a[j] - a[i];
      if (cnt[x] > 10) continue;
      int ok_i = 1, ok_j = 1;
      for (int k = 0; k < (cnt[x]); k++)
        if (b[x][k] == i) ok_i = 0;
      for (int k = 0; k < (cnt[x]); k++)
        if (b[x][k] == j) ok_j = 0;
      if (ok_i) b[x][cnt[x]++] = i;
      if (ok_j) b[x][cnt[x]++] = j;
    }
  int arr[13], c, vis[13];
  for (int i = 0; i < (1111111); i++)
    if (i) {
      c = 0;
      for (int j = i; c < 10 && j < 1111111; j += i) {
        for (int k = 0; k < (cnt[j]); k++)
          if (c < 10) {
            int ok = 1;
            for (int l = 0; l < (c); l++)
              if (arr[l] == a[b[j][k]]) ok = 0;
            if (ok) arr[c++] = a[b[j][k]];
          }
      }
      int total = c;
      memset(vis, 0, sizeof(vis));
      for (int k = 0; k < (c); k++)
        if (!vis[k]) {
          total--;
          for (int j = 0; j < (c); j++)
            if (j > k && arr[j] % i == arr[k] % i) vis[j] = 1;
        }
      if (total <= k) {
        cout << i << endl;
        return 0;
      }
    }
  return 0;
}

```