#include <bits/stdc++.h>
using namespace std;
clock_t start;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
struct MaxFlow {
  struct Edge {
    long long f;
    long long u;
    Edge* nex;
    Edge* rev;
    Edge(long long _u, long long _f, Edge* _nex) : f(_f), u(_u), nex(_nex) {}
  };
  vector<Edge*> g;
  MaxFlow(long long n) { g.resize(n); }
  void AddEdge(long long v, long long u, long long f) {
    g[v] = new Edge(u, f, g[v]);
    g[u] = new Edge(v, 0, g[u]);
    g[v]->rev = g[u];
    g[u]->rev = g[v];
  }
  long long Flow(long long src, long long sink, long long n) {
    long long flow = 0;
    while (true) {
      vector<Edge*> par(n);
      vector<bool> vis(n, false);
      vector<long long> mn(n, 0);
      queue<long long> q;
      q.push(src);
      vis[src] = 1;
      mn[src] = (long long)(2e18);
      while (!q.empty()) {
        long long v = q.front();
        q.pop();
        for (Edge* e = g[v]; e; e = e->nex) {
          if (e->f <= 0) continue;
          if (!vis[e->u]) {
            mn[e->u] = min(mn[v], e->f);
            par[e->u] = e;
            vis[e->u] = 1;
            q.push(e->u);
          }
        }
      }
      long long curr = sink;
      long long ff = mn[sink];
      if (ff == 0) break;
      flow += ff;
      while (curr != src) {
        Edge* e = par[curr];
        e->f -= ff;
        e->rev->f += ff;
        curr = e->rev->u;
      }
    }
    return flow;
  }
};
const long long N = 3e5 + 10;
bool pr[N];
void seive() {
  for (long long i = 2; i < N; i++) {
    if (pr[i]) continue;
    for (long long j = i + i; j < N; j += i) pr[j] = 1;
  }
}
void solve() {
  long long n, k;
  cin >> n >> k;
  long long p[n], c[n], l[n];
  for (long long i = 0; i < n; i++) {
    cin >> p[i] >> c[i] >> l[i];
  }
  long long s = 1, e = n, ans = -1;
  while (s <= e) {
    long long mid = (s + e) / 2, sum = 0;
    vector<pair<long long, long long> > edge;
    long long mx = 0;
    for (long long i = 0; i < n; i++) {
      if (l[i] <= mid && c[i] != 1) {
        sum += p[i];
        edge.push_back({p[i], c[i]});
      }
      if (c[i] == 1 && l[i] <= mid) {
        mx = max(mx, p[i]);
      }
    }
    if (mx) edge.push_back({mx, 1});
    sum += mx;
    MaxFlow M((long long)((edge).size()) + 4);
    long long src = (long long)((edge).size()),
              sink = (long long)((edge).size()) + 1;
    for (long long i = 0; i < (long long)((edge).size()); i++) {
      for (long long j = i + 1; j < (long long)((edge).size()); j++) {
        if (!pr[edge[i].second + edge[j].second]) {
          if (edge[i].second % 2)
            M.AddEdge(i, j, edge[i].first);
          else
            M.AddEdge(j, i, edge[j].first);
        }
      }
      if (edge[i].second % 2)
        M.AddEdge(src, i, edge[i].first);
      else
        M.AddEdge(i, sink, edge[i].first);
    }
    long long flow = M.Flow(src, sink, sink + 4);
    if (sum - flow >= k) {
      ans = mid;
      e = mid - 1;
    } else
      s = mid + 1;
  }
  cout << ans << '\n';
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  start = clock();
  cout << fixed << setprecision(20);
  seive();
  for (long long i = 1; i <= t; i++) {
    solve();
  }
  return 0;
}
