#include <bits/stdc++.h>
using namespace std;
int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x < y ? x : y; }
const int N = 10005;
const int M = 1000005;
int num[N], dis[M];
map<int, int> mp;
int n, m, tt;
bool judge(int mod) {
  if (mod == 0) return 0;
  mp.clear();
  for (int i = 0; i < n; i++) mp[num[i] % mod]++;
  if (mp.size() >= n - m) return 1;
  return 0;
}
int main() {
  int i, j, k = 1;
  while (scanf("%d%d", &n, &m) != EOF) {
    for (i = 0; i < n; i++) scanf("%d", &num[i]);
    if (n <= m + 1) {
      printf("1\n");
      continue;
    }
    sort(num, num + n);
    memset(dis, 0, sizeof(dis));
    for (i = 0; i < n; i++)
      for (j = i + 1; j < n; j++) dis[num[j] - num[i]]++;
    int Max = num[n - 1] + 1, sum, p = m * (m + 1) / 2;
    for (i = max(n - m, 1); i < Max; i++) {
      for (j = i, sum = 0; j < Max; j += i) sum += dis[j];
      if (sum > p) continue;
      if (judge(i)) break;
    }
    printf("%d\n", i);
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x < y ? x : y; }
const int N = 10005;
const int M = 1000005;
int num[N], dis[M];
map<int, int> mp;
int n, m, tt;
bool judge(int mod) {
  if (mod == 0) return 0;
  mp.clear();
  for (int i = 0; i < n; i++) mp[num[i] % mod]++;
  if (mp.size() >= n - m) return 1;
  return 0;
}
int main() {
  int i, j, k = 1;
  while (scanf("%d%d", &n, &m) != EOF) {
    for (i = 0; i < n; i++) scanf("%d", &num[i]);
    if (n <= m + 1) {
      printf("1\n");
      continue;
    }
    sort(num, num + n);
    memset(dis, 0, sizeof(dis));
    for (i = 0; i < n; i++)
      for (j = i + 1; j < n; j++) dis[num[j] - num[i]]++;
    int Max = num[n - 1] + 1, sum, p = m * (m + 1) / 2;
    for (i = max(n - m, 1); i < Max; i++) {
      for (j = i, sum = 0; j < Max; j += i) sum += dis[j];
      if (sum > p) continue;
      if (judge(i)) break;
    }
    printf("%d\n", i);
  }
  return 0;
}

```