#include <bits/stdc++.h>
using namespace std;
const int N = 5010, M = 1000100;
int n, m, c;
int cnt[M];
pair<int, int> q[M][12];
int len[M];
int a[N], v[M];
pair<int, int> r[100];
int abs(int n) { return n > 0 ? n : -n; }
int main() {
  scanf("%d%d", &n, &c);
  m = 0;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), m = max(m, a[i]);
  for (int i = 1; i < n; i++)
    for (int j = i + 1; j <= n; j++) {
      int t = abs(a[i] - a[j]);
      if (len[t] < 10) q[t][len[t]] = make_pair(i, j);
      len[t]++;
    }
  for (int i = 1; i <= m; i++) {
    int res = 0, all = 0;
    for (int j = i; j <= m; j += i) {
      if (all + len[j] > 10) {
        res = c + 1;
        break;
      }
      all += len[j];
      for (int k = 0; k < len[j]; k++) {
        if (v[q[j][k].first] != i) {
          v[q[j][k].first] = i;
          if (cnt[a[q[j][k].first] % i] != i)
            cnt[a[q[j][k].first] % i] = i;
          else
            res++;
        }
        if (v[q[j][k].second] != i) {
          v[q[j][k].second] = i;
          if (cnt[a[q[j][k].second] % i] != i)
            cnt[a[q[j][k].second] % i] = i;
          else
            res++;
        }
      }
      if (res > c) break;
    }
    if (res > c) continue;
    printf("%d\n", i);
    return 0;
  }
  printf("%d\n", m + 1);
  return 0;
}

### Prompt

Your task is to create 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;
const int N = 5010, M = 1000100;
int n, m, c;
int cnt[M];
pair<int, int> q[M][12];
int len[M];
int a[N], v[M];
pair<int, int> r[100];
int abs(int n) { return n > 0 ? n : -n; }
int main() {
  scanf("%d%d", &n, &c);
  m = 0;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), m = max(m, a[i]);
  for (int i = 1; i < n; i++)
    for (int j = i + 1; j <= n; j++) {
      int t = abs(a[i] - a[j]);
      if (len[t] < 10) q[t][len[t]] = make_pair(i, j);
      len[t]++;
    }
  for (int i = 1; i <= m; i++) {
    int res = 0, all = 0;
    for (int j = i; j <= m; j += i) {
      if (all + len[j] > 10) {
        res = c + 1;
        break;
      }
      all += len[j];
      for (int k = 0; k < len[j]; k++) {
        if (v[q[j][k].first] != i) {
          v[q[j][k].first] = i;
          if (cnt[a[q[j][k].first] % i] != i)
            cnt[a[q[j][k].first] % i] = i;
          else
            res++;
        }
        if (v[q[j][k].second] != i) {
          v[q[j][k].second] = i;
          if (cnt[a[q[j][k].second] % i] != i)
            cnt[a[q[j][k].second] % i] = i;
          else
            res++;
        }
      }
      if (res > c) break;
    }
    if (res > c) continue;
    printf("%d\n", i);
    return 0;
  }
  printf("%d\n", m + 1);
  return 0;
}

```