#include <bits/stdc++.h>
using namespace std;
int gap[1000005];
int N, K;
int seq[5005];
char lef[1000005];
int main() {
  int MM, cnt, sum;
  while (scanf("%d %d", &N, &K) != EOF) {
    MM = -1;
    memset(gap, 0, sizeof(gap));
    for (int i = 0; i < N; ++i) {
      scanf("%d", &seq[i]);
      MM = max(MM, seq[i]);
    }
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < i; ++j) {
        ++gap[abs(seq[i] - seq[j])];
      }
    }
    MM = MM + 1;
    int flag = 0;
    for (int m = 1; m <= MM && !flag; ++m) {
      cnt = sum = 0;
      for (int i = m; i <= MM; i += m) {
        sum += gap[i];
        if (sum > K * (K + 1) / 2) break;
      }
      if (sum > K * (K + 1) / 2) continue;
      flag = m;
      memset(lef, 0, sizeof(lef));
      for (int i = 0; i < N; ++i) {
        int k = seq[i] % m;
        if (!(lef[k]))
          lef[k] = 1;
        else if (++cnt > K) {
          flag = 0;
          break;
        }
      }
    }
    printf("%d\n", flag);
  }
  return 0;
}

### 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;
int gap[1000005];
int N, K;
int seq[5005];
char lef[1000005];
int main() {
  int MM, cnt, sum;
  while (scanf("%d %d", &N, &K) != EOF) {
    MM = -1;
    memset(gap, 0, sizeof(gap));
    for (int i = 0; i < N; ++i) {
      scanf("%d", &seq[i]);
      MM = max(MM, seq[i]);
    }
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < i; ++j) {
        ++gap[abs(seq[i] - seq[j])];
      }
    }
    MM = MM + 1;
    int flag = 0;
    for (int m = 1; m <= MM && !flag; ++m) {
      cnt = sum = 0;
      for (int i = m; i <= MM; i += m) {
        sum += gap[i];
        if (sum > K * (K + 1) / 2) break;
      }
      if (sum > K * (K + 1) / 2) continue;
      flag = m;
      memset(lef, 0, sizeof(lef));
      for (int i = 0; i < N; ++i) {
        int k = seq[i] % m;
        if (!(lef[k]))
          lef[k] = 1;
        else if (++cnt > K) {
          flag = 0;
          break;
        }
      }
    }
    printf("%d\n", flag);
  }
  return 0;
}

```