#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
const int INF = 1E9;
namespace mf {
struct Edge {
  int from, to, cap, flow;
  Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};
int h[MAXN], cur[MAXN];
vector<Edge> edges;
vector<int> g[MAXN];
void clear(int n) {
  edges.clear();
  for (int i = 1; i <= n; i++) g[i].clear();
}
inline void addEdge(int from, int to, int cap) {
  edges.push_back(Edge(from, to, cap, 0));
  edges.push_back(Edge(to, from, 0, 0));
  g[from].push_back(edges.size() - 2);
  g[to].push_back(edges.size() - 1);
}
bool bfs(int s, int t) {
  memset(cur, 0, sizeof cur);
  memset(h, 0, sizeof h);
  queue<int> que;
  h[s] = 1;
  que.push(s);
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    for (int i = 0; i < g[u].size(); i++) {
      Edge e = edges[g[u][i]];
      if (e.cap > e.flow && !h[e.to]) h[e.to] = h[u] + 1, que.push(e.to);
    }
  }
  return h[t];
}
int dfs(int u, int t, int f) {
  if (u == t) return f;
  for (int& i = cur[u]; i < g[u].size(); i++) {
    Edge& e = edges[g[u][i]];
    if (e.cap > e.flow && h[e.to] == h[u] + 1) {
      int d = dfs(e.to, t, min(f, e.cap - e.flow));
      if (d > 0) {
        e.flow += d;
        edges[g[u][i] ^ 1].flow -= d;
        return d;
      }
    }
  }
  return 0;
}
int dinic(int s, int t) {
  int flow = 0;
  while (bfs(s, t))
    while (int f = dfs(s, t, INF)) flow += f;
  return flow;
}
}  // namespace mf
struct Node {
  int p, c, l;
} a[MAXN];
int n, k;
bool isprime(int n) {
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) return 0;
  return 1;
}
bool check(int l) {
  mf::clear(n + 2);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (a[i].c & 1 && isprime(a[i].c + a[j].c)) mf::addEdge(i, j, INF);
  int sum = 0, mx = 0, id;
  for (int i = 1; i <= n; i++)
    if (a[i].l <= l)
      if (a[i].c != 1) {
        sum += a[i].p;
        if (a[i].c & 1)
          mf::addEdge(n + 1, i, a[i].p);
        else
          mf::addEdge(i, n + 2, a[i].p);
      } else if (a[i].p > mx)
        mx = a[i].p, id = i;
  if (mx) sum += mx, mf::addEdge(n + 1, id, mx);
  return sum - mf::dinic(n + 1, n + 2) >= k;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d%d%d", &a[i].p, &a[i].c, &a[i].l);
  int l = 1, r = n + 1;
  while (l < r) {
    int mid = l + r >> 1;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  printf("%d\n", l == n + 1 ? -1 : l);
  return 0;
}
