#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[5005], b[1000011], c[1000011], d[1000011];
int main() {
  scanf("%d %d", &n, &k);
  for (int p = (1); p <= (n); p += (1)) scanf("%d", &a[p]);
  sort(a + 1, a + n + 1);
  for (int p = (1); p <= (n); p += (1))
    for (int q = (p + 1); q <= (n); q += (1)) d[a[q] - a[p]]++;
  for (int p = (1); p <= (1000010); p += (1))
    for (int q = (p); q <= (1000010); q += (p)) c[p] += d[q];
  for (int m = 1;; m++)
    if (c[m] <= k * (k + 1) / 2) {
      bool flag = false;
      int cnt = 0;
      for (int p = (1); p <= (n); p += (1)) {
        if (0 != b[a[p] % m]) cnt++;
        if (cnt > k) {
          for (int q = (1); q <= (p - 1); q += (1)) b[a[q] % m]--;
          flag = true;
          p = n;
          break;
        } else
          b[a[p] % m]++;
      }
      if (!flag) {
        printf("%d", m);
        return 0;
      }
    }
}

### Prompt

Please formulate 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;
int n, k;
int a[5005], b[1000011], c[1000011], d[1000011];
int main() {
  scanf("%d %d", &n, &k);
  for (int p = (1); p <= (n); p += (1)) scanf("%d", &a[p]);
  sort(a + 1, a + n + 1);
  for (int p = (1); p <= (n); p += (1))
    for (int q = (p + 1); q <= (n); q += (1)) d[a[q] - a[p]]++;
  for (int p = (1); p <= (1000010); p += (1))
    for (int q = (p); q <= (1000010); q += (p)) c[p] += d[q];
  for (int m = 1;; m++)
    if (c[m] <= k * (k + 1) / 2) {
      bool flag = false;
      int cnt = 0;
      for (int p = (1); p <= (n); p += (1)) {
        if (0 != b[a[p] % m]) cnt++;
        if (cnt > k) {
          for (int q = (1); q <= (p - 1); q += (1)) b[a[q] % m]--;
          flag = true;
          p = n;
          break;
        } else
          b[a[p] % m]++;
      }
      if (!flag) {
        printf("%d", m);
        return 0;
      }
    }
}

```