#include <bits/stdc++.h>
using namespace std;
const int maxn = 102, maxsize = 2e5 + 1, INF = 1e8;
int n, k, p[maxn], c[maxn], l[maxn], mark[maxsize + 10], prime[maxsize + 10],
    max1, sum, s, t, tot, head[3 * maxn], dep[3 * maxn], q[3 * maxn], ans;
struct Edge {
  int ss, e, nex, w, flow;
} edge[maxn * maxn];
void add(int ss, int ee, int w) {
  edge[++tot] = {ss, ee, head[ss], w, 0};
  head[ss] = tot;
  edge[++tot] = {ee, ss, head[ee], 0, 0};
  head[ee] = tot;
}
bool find() {
  memset(dep, 0, sizeof(dep));
  int l, r, cur;
  l = r = 1;
  q[1] = s;
  dep[s] = 1;
  while (l <= r) {
    cur = q[l++];
    for (int i = head[cur], e; i; i = edge[i].nex) {
      e = edge[i].e;
      if (edge[i].flow < edge[i].w && !dep[e]) {
        q[++r] = e;
        dep[e] = dep[cur] + 1;
        if (e == t) return true;
      }
    }
  }
  return false;
}
int dfs(int cur, int now) {
  if (cur == t || now <= 0) return now;
  int tt = now, delta;
  for (int i = head[cur], e; i; i = edge[i].nex) {
    e = edge[i].e;
    if (edge[i].w > edge[i].flow && dep[e] == dep[cur] + 1) {
      delta = dfs(e, min(tt, edge[i].w - edge[i].flow));
      if (delta <= 0) dep[e] = 0;
      edge[i].flow += delta;
      edge[((i - 1) ^ 1) + 1].flow -= delta;
      tt -= delta;
      if (tt == 0) break;
    }
  }
  return now - tt;
}
void dinic() {
  ans = 0;
  while (find()) ans += dfs(s, INF * 5);
}
void init() {
  int index = 0;
  memset(mark, 0, sizeof(mark));
  for (int i = 2; i < maxsize; i++) {
    if (mark[i] == 0) prime[index++] = i;
    for (int j = 0; j < index && prime[j] * i < maxsize; j++) {
      mark[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
  return;
}
bool check(int lmax) {
  memset(head, 0, sizeof(head));
  memset(edge, 0, sizeof(edge));
  tot = 0;
  max1 = 0;
  sum = 0;
  for (int i = 1; i <= n; i++) {
    if (l[i] > lmax) continue;
    if (c[i] == 1) {
      if (p[i] > p[max1]) max1 = i;
      continue;
    }
    sum += p[i];
    if (c[i] % 2 == 1)
      add(s, i, p[i]);
    else
      add(i, t, p[i]);
  }
  if (max1) {
    add(s, max1, p[max1]);
    sum += p[max1];
  }
  for (int i = 1; i <= n; i++) {
    if (c[i] == 1 && i != max1) continue;
    if (c[i] % 2 == 1 && l[i] <= lmax)
      for (int j = 1; j <= n; j++)
        if (c[j] % 2 == 0 && l[j] <= lmax)
          if (mark[c[i] + c[j]] == false) add(i, j, INF);
  }
  dinic();
  ans = sum - ans;
  return ans >= k;
}
int main() {
  init();
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d%d%d", &p[i], &c[i], &l[i]);
  s = n + 1;
  t = n + 2;
  int l = 1, r = n, mid;
  while (l < r) {
    mid = (l + r) / 2;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  if (check(l) == false)
    printf("-1\n");
  else
    printf("%d\n", l);
  return 0;
}
