#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
using namespace std;
int ya[2000][2000],yd[2000][2000]={0},n;
int zhao(int a,int b)
{
	int c;
	for(;;)
	{
		c=a%b;
		if(c==0)
		{
			if(b==1)
				return 1;
			else return 0;
		}
		a=b;b=c;
	}
}
int main(){
	freopen ("tarmy.in","r",stdin);
	freopen ("tarmy.out","w",stdout);
	int yb[10000]={0},yc[10000]={0},jia[10000]={0};
	int a,b,c,d,e,f,g,k;
	cin>>n>>k;
	for(a=1;a<=n;a++)
	{
		cin>>yb[a];
	}
	for(a=1;a<=n;a++)
	{
		for(b=1;b<=n;b++)
		{
			if(a==b)
				continue;
			f=zhao(max(yb[a],yb[b]),min(yb[a],yb[b]));
			if(a!=b&&f==1)
			{
				ya[yb[a]][yb[b]]=1;
				jia[a]++;
				yc[a]=yc[a]+yb[b];
				yd[a][jia[a]]=yb[b];
			}
		}
		yc[a]=yc[a]+yb[a];
	}
	for(a=1;a<=n;a++)
	{
		if(yc[a]>=k)
		{
			for(b=1;b<=jia[a];b++)
			{
				if(yd[a][b]!=0)
				{
					for(c=b+1;c<=jia[a];c++)
					{
						if(ya[yd[a][b]][yd[a][c]]==0)
						{
							if(yd[a][b]>yd[a][c])
							{
								yd[a][c]=0;
							}
							else
							{
								yd[a][b]=yd[a][c];
								yd[a][c]=0;
							}
						}
					}
				}
			}
		}
	}
	d=0;
	int ans,ansb;
	ans=0;
	for(a=1;a<=n;a++)
	{
		ansb=0;
		e=0;
		for(b=1;b<=jia[a];b++)
		{
			if(yd[a][b]!=0)
			{
				ansb=ansb+yd[a][b];
				e++;
			}
		}
		e=e+1;
		ansb=ansb+yb[a];
		if(ansb>=k)
			ans=max(ans,e);
	}
	cout<<ans;
	return 0;
}