#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;
int pri[200002];
int p_ct;
bool mark[200002];
inline void ini_p(int x) {
  for (int i = 2; i <= x; ++i) {
    if (!mark[i]) {
      pri[++p_ct] = i;
    }
    for (int j = 1; j <= p_ct; ++j) {
      if (i * pri[j] > x) break;
      mark[i * pri[j]] = 1;
      if (i % pri[j] == 0) break;
    }
  }
}
namespace Flow {
int S, T, nd_ct;
struct edge {
  int np, cap, next;
} e[102 * 102 << 1];
int head[102];
int e_ct = 1;
inline void adde(int u, int v, int cap) {
  e[++e_ct] = (edge){v, cap, head[u]};
  head[u] = e_ct;
  e[++e_ct] = (edge){u, 0, head[v]};
  head[v] = e_ct;
}
inline void ini(int x) {
  e_ct = 1, nd_ct = x;
  memset(head, 0, sizeof(int) * (x + 1));
}
int dis[102];
int qu[102], ql, qr;
inline bool bfs() {
  for (int i = 0; i <= nd_ct; ++i) dis[i] = -1;
  ql = qr = 0;
  qu[qr++] = S;
  dis[S] = 0;
  while (ql < qr) {
    int x = qu[ql++];
    for (int ne = head[x]; ne; ne = e[ne].next) {
      int cur = e[ne].np;
      if (e[ne].cap && !~dis[cur]) {
        dis[cur] = dis[x] + 1;
        qu[qr++] = cur;
      }
    }
  }
  return dis[T] != -1;
}
inline int dfs(int x, int f) {
  if (x == T) return f;
  int a = 0;
  for (int ne = head[x]; ne; ne = e[ne].next) {
    int cur = e[ne].np;
    if (e[ne].cap && dis[cur] == dis[x] + 1) {
      int t = dfs(cur, min(f, e[ne].cap));
      a += t, f -= t;
      e[ne].cap -= t;
      e[ne ^ 1].cap += t;
      if (!f) return a;
    }
  }
  if (a == 0) dis[x] = -1;
  return a;
}
inline int dinic() {
  int as = 0;
  while (bfs()) as += dfs(S, INF);
  return as;
}
}  // namespace Flow
struct card {
  int p, c, l;
  bool operator<(const card& x) const {
    if (c != 1 && x.c != 1) return l < x.l;
    if (c == 1 && x.c != 1) return 1;
    if (c != 1 && x.c == 1) return 0;
    if (l == x.l) return p > x.p;
    return l < x.l;
  }
} ca[102];
int n, k;
int vs[102];
int a[102], b[102];
int a_ct, b_ct, tot;
inline bool sol(int l, int r, int level) {
  using namespace Flow;
  ini(r - l + 3);
  S = 0, T = nd_ct;
  tot = a_ct = b_ct = 0;
  for (int i = l; i <= r; ++i) {
    if (ca[i].c & 1)
      a[++a_ct] = i;
    else
      b[++b_ct] = i;
  }
  if (vs[level]) a[++a_ct] = -1;
  for (int i = 1; i <= a_ct; ++i) {
    for (int j = 1; j <= b_ct; ++j) {
      int t = (~a[i] ? ca[a[i]].c : 1) + ca[b[j]].c;
      if (!mark[t]) adde(i, j + a_ct, INF);
    }
  }
  for (int i = 1; i <= a_ct; ++i) {
    adde(S, i, ~a[i] ? ca[a[i]].p : vs[level]);
    tot += ~a[i] ? ca[a[i]].p : vs[level];
  }
  for (int i = 1; i <= b_ct; ++i) {
    adde(a_ct + i, T, ca[b[i]].p);
    tot += ca[b[i]].p;
  }
  tot -= dinic();
  return tot >= k;
}
int mx1, mx2;
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d%d", &ca[i].p, &ca[i].c, &ca[i].l);
    if (ca[i].c > mx1)
      mx2 = mx1, mx1 = ca[i].c;
    else if (ca[i].c > mx2)
      mx2 = ca[i].c;
  }
  ini_p(mx1 + mx2);
  sort(ca + 1, ca + 1 + n);
  int idx = n + 1;
  for (int i = 1; i <= n; ++i) {
    if (ca[i].c != 1) {
      idx = i;
      break;
    }
    if (ca[i].l != ca[i - 1].l) vs[ca[i].l] = ca[i].p;
  }
  for (int i = 2; i <= n; ++i) vs[i] = max(vs[i], vs[i - 1]);
  int tas = -1;
  for (int i = 1; i <= n; ++i) {
    if (vs[i] >= k) {
      tas = i;
      break;
    }
  }
  for (int i = idx; i <= n; ++i) {
    if (ca[i].l != ca[i + 1].l) {
      bool can = sol(idx, i, ca[i].l);
      if (can) {
        printf("%d\n", ca[i].l);
        return 0;
      }
    }
  }
  if (~tas) {
    printf("%d\n", tas);
    return 0;
  }
  printf("-1\n");
  return 0;
}
