#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mkp make_pair
#define pb push_back
#define fir first
#define pp pop_back
#define eps 1e-8
#define sec second
#define pii pair<int,int>
#define eb emplace_back
#define file(filename) freopen(filename".in","r",stdin);freopen(filename".out","w",stdout);
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Dor(i,a,b) for(int i=a;i>=b;i--)
//==============================================================================================
// Fast IO

template<typename T>
inline void read(T &a){
	T f=1,c=0;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(isdigit(ch)){
		c=(c<<1)+(c<<3)+(ch^48);
		ch=getchar();
	}
	a=f*c;
}
template<typename T,typename... Args>
void read(T &x,Args &...args){
	read(x),read(args...);
}

//=============================================================================================
//code here
#define int long long
const int N=1e3+10;
struct edge{
	int nxt,to,w;
}e[N<<4];
int n,k;
int head[N<<1],cnt=1;int maxflow=0,cur[N<<1];
void add(int u,int v,int w){
	e[++cnt]={head[u],v,w};
	head[u]=cnt;
}
int s,t;
int dis[N<<1];
void bfs(){
	memset(dis,-1,sizeof(dis));
	queue<int> q;
	q.push(s);
	dis[s]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];~i;i=e[i].nxt){
			int to=e[i].to,w=e[i].w;
			if(!w){
				continue;
			}
			if(!~dis[to]){
				dis[to]=dis[u]+1;
				q.push(to);
			}
		}
	}
}
int dfs(int u,int sum){
	if(u==t||sum==0){
		return sum;
	}
	int tmp=sum;
	for(int &i=cur[u];~i;i=e[i].nxt){
		int to=e[i].to,w=e[i].w;
		if(!w){
			continue;
		}
		if(dis[to]!=dis[u]+1){
			continue;
		}
		int t=dfs(to,min(tmp,w));
		if(t==0){
			dis[to]=0;
		}
		else{
			e[i].w-=t;
			e[i^1].w+=t;
			tmp-=t;
		}
	}
	return sum-tmp;
}

void dinic(){
	while(1){
		bfs();
		if(!~dis[t]){
			return;
		}
		memcpy(cur,head,sizeof(cur));
		maxflow+=dfs(s,inf);
	}
}
bool check(int x){
	for(int i=2;i*i<=n;i++){
		if(n%i==0){
			return 0;
		}
	}
	return 1;
}
struct node{
	int p,c,l;
}a[N];
int ans;
bool solve(int l){
	maxflow=0;
	memset(head,-1,sizeof(head));
	cnt=1;
	ans=0;
	For(i,1,n){
		if(a[i].l>l){
			continue;
		}
		if(a[i].c&1){
			if(a[i].c!=1){
				add(s,i,a[i].p);
				add(i,s,0);
				ans+=a[i].p;
			}
		}
		else{
			add(i,t,a[i].p);
			add(t,i,0);
			ans+=a[i].p;
		}
	}
	For(i,1,n){
		For(j,1,n){
			if(a[i].l>l||a[j].l>l||!(a[i].c&1)||a[j].c&1||!check(a[i].c+a[j].c)||a[i].c==1||a[j].c==1){
				continue;
			}
			add(i,j,inf);
			add(j,i,0);
		}
	}
	int maxn=0,pos=0;
	For(i,1,n){
		if(a[i].l<=l&&a[i].c==1&&a[i].p>maxn){
			maxn=a[i].p;
			pos=i;
		}
	}
	if(pos){
		ans+=maxn;
		add(s,pos,maxn);
		add(pos,s,0);
		For(i,1,n){
			if(!(a[i].c&1)&&check(a[i].c+1)){
				add(pos,i,inf);
				add(i,pos,0);
			}
		}
	}
	dinic();
	return ans-maxflow>=k;
}
signed main(){
	cin>>n>>k;
	For(i,1,n){
		cin>>a[i].p>>a[i].c>>a[i].l;
	}
	s=n+2,t=n+1;
	int l=1,r=n+1,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(solve(mid)){
			ans=mid;
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	cout<<((ans==0)?-1:ans)<<endl;
}
//正难则反
//是否考虑了所有情况