#include <bits/stdc++.h>
using namespace std;
namespace Euler {
const int N = 2e5 + 7;
int primes[N], tot = 0;
bool vis[N];
void euler() {
  memset(vis, 0, sizeof(vis));
  for (int i = 2; i <= N; i++) {
    if (!vis[i]) primes[++tot] = i;
    for (int j = 1; j <= tot; j++) {
      if (i * primes[j] > N) break;
      vis[i * primes[j]] = 1;
      if (i % primes[j] == 0) break;
    }
  }
}
}  // namespace Euler
namespace ISAP {
const int N = 120, inf = ~0U >> 2, M = 20000;
struct edge {
  int t, f;
  edge *nxt, *pair;
} * g[N], *d[N], pool[M], *cur = pool;
int i, S, T, h[N], gap[N], maxflow;
void init(int ss, int tt) {
  for (S = ss, T = tt, cur = pool, i = 1; i <= T; i++)
    g[i] = d[i] = NULL, h[i] = gap[i] = 0;
}
void add(int s, int t, int f) {
  edge* p = cur++;
  p->t = t, p->f = f, p->nxt = g[s], g[s] = p;
  p = cur++, p->t = s, p->f = 0, p->nxt = g[t], g[t] = p;
  g[s]->pair = g[t], g[t]->pair = g[s];
}
int sap(int v, int flow) {
  if (v == T) return flow;
  int rec = 0;
  for (edge* p = d[v]; p; p = p->nxt)
    if (h[v] == h[p->t] + 1 && p->f) {
      int ret = sap(p->t, min(flow - rec, p->f));
      p->f -= ret;
      p->pair->f += ret;
      d[v] = p;
      if ((rec += ret) == flow) return flow;
    }
  if (!(--gap[h[v]])) h[S] = T;
  gap[++h[v]]++;
  d[v] = g[v];
  return rec;
}
int get_ans() {
  for (gap[maxflow = 0] = T, i = 1; i <= T; i++) d[i] = g[i];
  while (h[S] < T) maxflow += sap(S, inf);
  return maxflow;
}
}  // namespace ISAP
int n, k;
struct node {
  int p, c, l;
  node(int a = 0, int b = 0, int _c = 0) : p(a), c(b), l(_c) {}
  void show() { printf("p=%d,c=%d,l=%d\n", p, c, l); }
} a[200], tmp[200];
bool Find(int x) {
  using namespace Euler;
  int now = lower_bound(primes + 1, primes + 1 + tot, x) - primes;
  if (now <= tot && x == primes[now]) return 1;
  return 0;
}
int check(int mid) {
  using namespace ISAP;
  int ed = 0, sum = 0, mxp = 0, mxidx = -1;
  for (int i = 1; i <= n; i++)
    if (a[i].l <= mid) {
      if (a[i].c == 1) {
        if (a[i].p > mxp) mxp = a[i].p, mxidx = i;
      } else
        tmp[++ed] = a[i], sum += a[i].p;
    }
  if (mxidx != -1) tmp[++ed] = a[mxidx], sum += a[mxidx].p;
  init(ed + 1, ed + 2);
  for (int i = 1; i <= ed; i++)
    if (tmp[i].c & 1)
      add(S, i, tmp[i].p);
    else
      add(i, T, tmp[i].p);
  for (int i = 1; i <= ed; i++)
    if (tmp[i].c & 1) {
      for (int j = 1; j <= ed; j++)
        if (tmp[j].c % 2 == 0 && Find(tmp[i].c + tmp[j].c)) add(i, j, inf);
    }
  int ansflow = get_ans();
  return sum - ansflow >= k;
}
int main() {
  Euler::euler();
  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, mid, ans = -1;
  while (l <= r) {
    mid = l + r >> 1;
    if (check(mid))
      r = mid - 1, ans = mid;
    else
      l = mid + 1;
  }
  printf("%d\n", ans);
  return 0;
}
