#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int N, K, A[5000];
int d[1000001], tmp[1000001];
int main() {
  scanf("%d%d", &N, &K);
  for (int(i) = 0; (i) < (N); (i)++) scanf("%d", &A[i]);
  sort(A, A + N);
  for (int(i) = 0; (i) < (N); (i)++)
    for (int(j) = 0; (j) < (i); (j)++) d[A[i] - A[j]]++;
  for (int ans = 1;; ans++) {
    int p = 0;
    for (int i = ans; i <= 1000000; i += ans) p += d[i];
    if (p > K * (K + 1) / 2) continue;
    memset(tmp, 0, sizeof(tmp));
    int k = 0, lasi = -1;
    for (int(i) = 0; (i) < (N); (i)++) {
      lasi = i;
      if (tmp[A[i] % ans]++) k++;
      if (k > K) break;
    }
    for (int(i) = 0; (i) < (lasi + 1); (i)++) tmp[A[i] % ans]--;
    if (k <= K) {
      printf("%d\n", ans);
      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;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int N, K, A[5000];
int d[1000001], tmp[1000001];
int main() {
  scanf("%d%d", &N, &K);
  for (int(i) = 0; (i) < (N); (i)++) scanf("%d", &A[i]);
  sort(A, A + N);
  for (int(i) = 0; (i) < (N); (i)++)
    for (int(j) = 0; (j) < (i); (j)++) d[A[i] - A[j]]++;
  for (int ans = 1;; ans++) {
    int p = 0;
    for (int i = ans; i <= 1000000; i += ans) p += d[i];
    if (p > K * (K + 1) / 2) continue;
    memset(tmp, 0, sizeof(tmp));
    int k = 0, lasi = -1;
    for (int(i) = 0; (i) < (N); (i)++) {
      lasi = i;
      if (tmp[A[i] % ans]++) k++;
      if (k > K) break;
    }
    for (int(i) = 0; (i) < (lasi + 1); (i)++) tmp[A[i] % ans]--;
    if (k <= K) {
      printf("%d\n", ans);
      return 0;
    }
  }
}

```