#include <bits/stdc++.h>
using namespace std;
const int MAX = 1 << 26;
const int N = 300101;
struct Edge {
  int u, v, c;
  int next;
} edge[N];
int n, m, k;
int edn;
int p[N];
int d[N];
int sp, tp;
void addedge(int u, int v, int c) {
  edge[edn].u = u;
  edge[edn].v = v;
  edge[edn].c = c;
  edge[edn].next = p[u];
  p[u] = edn++;
  edge[edn].u = v;
  edge[edn].v = u;
  edge[edn].c = 0;
  edge[edn].next = p[v];
  p[v] = edn++;
}
int bfs() {
  queue<int> q;
  memset(d, -1, sizeof(d));
  d[sp] = 0;
  q.push(sp);
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (int i = p[cur]; i != -1; i = edge[i].next) {
      int u = edge[i].v;
      if (d[u] == -1 && edge[i].c > 0) {
        d[u] = d[cur] + 1;
        q.push(u);
      }
    }
  }
  return d[tp] != -1;
}
int dfs(int a, int b) {
  int r = 0;
  if (a == tp) return b;
  for (int i = p[a]; i != -1 && r < b; i = edge[i].next) {
    int u = edge[i].v;
    if (edge[i].c > 0 && d[u] == d[a] + 1) {
      int x = min(edge[i].c, b - r);
      x = dfs(u, x);
      r += x;
      edge[i].c -= x;
      edge[i ^ 1].c += x;
    }
  }
  if (!r) d[a] = -2;
  return r;
}
int dinic(int sp, int tp) {
  int total = 0, t;
  while (bfs()) {
    while (t = dfs(sp, MAX)) total += t;
  }
  return total;
}
int i, a[N], b[N], c[N], flag[N], j;
int l, r;
vector<int> vec;
int main() {
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n; i++) {
    scanf("%d%d%d", &a[i], &b[i], &c[i]);
  }
  for (i = 2; i <= 200000; i++)
    if (flag[i] == 0)
      for (j = 2 * i; j <= 200000; j += i) flag[j] = 1;
  l = 1;
  r = n;
  while (l <= r) {
    m = (l + r) >> 1;
    vec.clear();
    int tmp = 0;
    edn = 0;
    memset(p, -1, sizeof(p));
    for (i = 1; i <= n; i++)
      if (c[i] <= m) {
        if (b[i] == 1) {
          if (tmp == 0)
            tmp = i;
          else if (a[i] > a[tmp])
            tmp = i;
        } else
          vec.push_back(i);
      }
    sp = 0;
    tp = n + 1;
    if (tmp) vec.push_back(tmp);
    int sum = 0;
    for (i = 0; i < vec.size(); i++) {
      if (b[vec[i]] % 2 == 0)
        addedge(sp, vec[i], a[vec[i]]);
      else
        addedge(vec[i], tp, a[vec[i]]);
      sum = sum + a[vec[i]];
    }
    for (i = 0; i < vec.size(); i++)
      if (b[vec[i]] % 2 == 0)
        for (j = 0; j < vec.size(); j++)
          if (b[vec[j]] % 2 == 1)
            if (flag[b[vec[i]] + b[vec[j]]] == 0) addedge(vec[i], vec[j], MAX);
    if (sum - dinic(sp, tp) >= k)
      r = m - 1;
    else
      l = m + 1;
  }
  if (l == n + 1) l = -1;
  printf("%d\n", l);
}
