N个不同的数a[1],a[2]...a[n]，你可以从中去掉K个数，并且找到一个正整数M，使得剩下的N - K个数，Mod M的结果各不相同，求M的最小值。

Input

第1行：2个数N, K，中间用空格分隔，N表示元素的数量，K为可以移除的数的数量(1 <= N <= 5000, 0 <= K <= 4, 1 <= a[i] <= 1000000)。

Output

输出符合条件的最小的M。

Input示例

5 112101112

Output示例

4 ———————————————————————— 如果a%mod==b%mod 那么(a-b)%mod==0 所以我们可以枚举mod 然后一波剪枝水过QAQ

#include
        
         #include
         
          #include
          
           using namespace std;const int M=1e5+7,N=1000007;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
      if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int n,k,mx,v[M],vis[N],f[N];int main(){    n=read(); k=read();    if(n+1<=k) return puts("1"),0;    for(int i=1;i<=n;i++) v[i]=read(),mx=max(mx,v[i]);    sort(v+1,v+1+n);    for(int i=1;i<=n;i++)        for(int j=i+1;j<=n;j++)            f[v[j]-v[i]]++;    for(int i=n-k;i<=mx;i++){        int cnt=0;        for(int j=1;i*j<=mx;j++) cnt+=f[i*j];        if(cnt>(k*(k+1)>>1)) continue;        cnt=0;        for(int j=1;j<=n;j++){            int now=v[j]%i;            if(vis[now]!=i) vis[now]=i;            else cnt++;        }        if(cnt<=k) return printf("%d\n",i),0;    }    return 0;}