#include <bits/stdc++.h>
using namespace std;
bool hash[2000010];
int h[2000010], pa[2000010];
int a[10002];
int n, k, i, j, limited, maxx, tmp, sum;
bool flag;
bool check(int x) {
  int i, rec, tmp;
  rec = 0;
  for (i = 1; i <= n; ++i) {
    tmp = a[i] % x;
    if (h[tmp] == x)
      rec++;
    else
      h[tmp] = x;
  }
  if (rec > k) return false;
  return true;
}
int main() {
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
  sort(a + 1, a + n + 1);
  limited = a[n] + 1;
  for (i = 1; i <= n; ++i)
    for (j = 1; j <= i - 1; ++j) pa[a[i] - a[j]]++;
  limited = a[n] + 1;
  maxx = (k + 1) * k / 2;
  for (i = 1; i <= limited; ++i) {
    sum = 0;
    tmp = limited / i;
    for (j = 0; j <= tmp; ++j) sum = sum + pa[i * j];
    if (sum <= k) {
      printf("%d\n", i);
      break;
    };
    if (sum > maxx) continue;
    if (check(i)) {
      printf("%d\n", i);
      break;
    }
  }
}

### 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>
using namespace std;
bool hash[2000010];
int h[2000010], pa[2000010];
int a[10002];
int n, k, i, j, limited, maxx, tmp, sum;
bool flag;
bool check(int x) {
  int i, rec, tmp;
  rec = 0;
  for (i = 1; i <= n; ++i) {
    tmp = a[i] % x;
    if (h[tmp] == x)
      rec++;
    else
      h[tmp] = x;
  }
  if (rec > k) return false;
  return true;
}
int main() {
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
  sort(a + 1, a + n + 1);
  limited = a[n] + 1;
  for (i = 1; i <= n; ++i)
    for (j = 1; j <= i - 1; ++j) pa[a[i] - a[j]]++;
  limited = a[n] + 1;
  maxx = (k + 1) * k / 2;
  for (i = 1; i <= limited; ++i) {
    sum = 0;
    tmp = limited / i;
    for (j = 0; j <= tmp; ++j) sum = sum + pa[i * j];
    if (sum <= k) {
      printf("%d\n", i);
      break;
    };
    if (sum > maxx) continue;
    if (check(i)) {
      printf("%d\n", i);
      break;
    }
  }
}

```