Digital collectible card games have become very popular recently. So Vova decided to try one of these.

Vova has n cards in his collection. Each of these cards is characterised by its power pi, magic number ci and level li. Vova wants to build a deck with total power not less than k, but magic numbers may not allow him to do so — Vova can't place two cards in a deck if the sum of the magic numbers written on these cards is a prime number. Also Vova cannot use a card if its level is greater than the level of Vova's character.

At the moment Vova's character's level is 1. Help Vova to determine the minimum level he needs to reach in order to build a deck with the required total power.

Input

The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 100000).

Then n lines follow, each of these lines contains three numbers that represent the corresponding card: pi, ci and li (1 ≤ pi ≤ 1000, 1 ≤ ci ≤ 100000, 1 ≤ li ≤ n).

Output

If Vova won't be able to build a deck with required power, print  - 1. Otherwise print the minimum level Vova has to reach in order to build a deck.

Examples

Input

5 8
5 5 1
1 5 4
4 6 3
1 12 4
3 12 1


Output

4


Input

3 7
4 4 1
5 8 2
5 3 3


Output

2
import java.io.*;
import java.util.*;

public class Main{
	static final int INF = (int)1e9;
	static int V, s, t;			//s != t
	static ArrayList<Integer>[] adjList;
	static int[][] res;			//instead of res, you can use c[][], f[][] so as not to destroy the graph
	static int[] p;				//res (residual) = c (capacity) - f (flow)
	
	static int edmondsKarp()	//O(min(VE^2, flow * E)) for adjList, O(V^3E)
	{
		int mf = 0;
		while(true)
		{
			Queue<Integer> q = new LinkedList<Integer>();
			p = new int[V];
			Arrays.fill(p, -1);
			q.add(s);
			p[s] = s;
			while(!q.isEmpty())
			{
				int u = q.remove();
				if(u == t)
					break;
				for(int v: adjList[u])
					if(res[u][v] > 0 && p[v] == -1)
					{
						p[v] = u;
						q.add(v);
					}
			}
			
			if(p[t] == -1)
				break;
			mf += augment(t, INF);	
		}
		return mf;
	}
	
	static int augment(int v, int flow)
	{
		if(v == s)
			return flow;
		flow =  augment(p[v], Math.min(flow, res[p[v]][v]));
		res[p[v]][v] -= flow;
		res[v][p[v]] += flow;
		
		return flow;
	}
	static boolean[] isComposite;
	
	
	static void sieve(int N)	// O(N log log N) 
	{
		isComposite = new boolean[N+1];					
		isComposite[0] = isComposite[1] = true;

		for (int i = 2; i <= N; ++i) 					
			if (!isComposite[i]) 					
			{
				if(1l * i * i <= N)
					for (int j = i * i; j <= N; j += i)	
						isComposite[j] = true;
			}   
	}
	static void addEdge(int i,int j,int cost) {
		adjList[i].add(j);
		adjList[j].add(i);
		res[i][j]=cost;
	}
	public static void main(String[] args) throws Exception{
		PrintWriter pw=new PrintWriter(System.out);
		MScanner sc = new MScanner(System.in);
		sieve(200000);
		int n=sc.nextInt(),k=sc.nextInt();
		int[][]in=new int[n][3];
		for(int i=0;i<n;i++) {
			in[i]=sc.intArr(3);
		}
		int ans=-1;
		
		int lo=1,hi=n;
		V=n+2;
		s=V-2;t=V-1;
		while(lo<=hi) {
			int lvl=(lo+hi)>>1;
			boolean[]valid=new boolean[n];
			
			for(int i=0;i<n;i++) {
				valid[i]=(in[i][2]<=lvl);
			}
			int maxOne=-1,max=0;
			for(int i=0;i<n;i++) {
				if(in[i][1]==1 && valid[i]) {
					if(in[i][0]>max) {
						max=in[i][0];
						maxOne=i;
					}
				}
			}
			for(int i=0;i<n;i++) {
				if(in[i][1]==1 && valid[i] && i!=maxOne) {
					valid[i]=false;
				}
			}
			res=new int[V][V];
			adjList=new ArrayList[V];
			for(int i=0;i<V;i++)adjList[i]=new ArrayList<>();
			int total=0;
			for(int i=0;i<n;i++) {
				if(!valid[i])continue;
				for(int j=0;j<n;j++) {
					if(!valid[j])continue;
					if(isComposite[in[i][1]+in[j][1]])continue;
					
					if(in[i][1]%2==0) {
						addEdge(i, j, INF);
					}
					else {
						addEdge(j, i, INF);
					}
				}
				
				if(in[i][1]%2==0) {
					addEdge(s, i, in[i][0]);
				}
				else {
					addEdge(i, t, in[i][0]);
				}
				total+=in[i][0];
			}
			int totPower=total-edmondsKarp();
			if(totPower>=k) {
				ans=lvl;
				hi=lvl-1;
				
			}
			else {
				lo=lvl+1;
			}
		}
		pw.println(ans);
		
		pw.flush();
	}
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] longArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public int[] intSortedArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public long[] longSortedArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		static void shuffle(int[]in) {
			for(int i=0;i<in.length;i++) {
				int idx=(int)(Math.random()*in.length);
				int tmp=in[i];
				in[i]=in[idx];
				in[idx]=tmp;
			}
		}
		static void shuffle(long[]in) {
			for(int i=0;i<in.length;i++) {
				int idx=(int)(Math.random()*in.length);
				long tmp=in[i];
				in[i]=in[idx];
				in[idx]=tmp;
			}
		}
		public Integer[] IntegerArr(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] LongArr(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
	static void addX(int[]in,int x) {
		for(int i=0;i<in.length;i++)in[i]+=x;
	}
	static void addX(long[]in,int x) {
		for(int i=0;i<in.length;i++)in[i]+=x;
	}
}