#include <bits/stdc++.h>
using namespace std;
struct edge {
  int f, c, from, to;
};
struct card {
  int pwr, num, lev;
};
int inf = 1e9;
int n, m, s, t;
vector<vector<int>> g;
vector<edge> e;
vector<int> dist;
vector<int> p;
vector<card> cards;
vector<char> prime;
void add_edge(int u, int v, int cap) {
  e.push_back(edge{0, cap, u, v});
  e.push_back(edge{0, 0, v, u});
  g[u].push_back(e.size() - 2);
  g[v].push_back(e.size() - 1);
}
int bfs(int cmin) {
  dist.assign(n, inf);
  dist[s] = 0;
  queue<int> q;
  q.push(s);
  while (q.size() > 0) {
    int v = q.front();
    q.pop();
    for (int i : g[v]) {
      if (e[i].c - e[i].f < cmin) continue;
      if (dist[e[i].to] > dist[v] + 1) {
        dist[e[i].to] = dist[v] + 1;
        q.push(e[i].to);
      }
    }
  }
  return dist[t];
}
int dfs(int v, int cmin, int add) {
  if (v == t) {
    return cmin;
  }
  for (; p[v] < g[v].size(); p[v]++) {
    int i = g[v][p[v]];
    if (dist[e[i].to] != dist[v] + 1) continue;
    if (e[i].c - e[i].f < cmin) continue;
    int added = dfs(e[i].to, cmin, min(add, e[i].c - e[i].f));
    if (added > 0) {
      e[i].f += added;
      e[i ^ 1].f -= added;
      return added;
    }
  }
  return 0;
}
int mincut() {
  int flow = 0;
  for (int cmin = 1000; cmin > 0; cmin /= 2) {
    while (bfs(cmin) != inf) {
      p.assign(n, 0);
      int added = 0;
      do {
        added = dfs(s, cmin, inf);
        flow += added;
      } while (added > 0);
    }
  }
  return flow;
}
int max_pow(int l) {
  vector<int> lp;
  vector<int> rp;
  int max_i = -1;
  int max_pwr = 0;
  for (int i = 0; i < cards.size(); i++) {
    if (cards[i].num != 1 || cards[i].lev > l) continue;
    if (cards[i].pwr > max_pwr) {
      max_i = i;
      max_pwr = cards[i].pwr;
    }
  }
  if (max_i != -1) rp.push_back(max_i);
  for (int i = 0; i < cards.size(); i++) {
    if (cards[i].num == 1 || cards[i].lev > l) continue;
    if (cards[i].num % 2 == 0) {
      lp.push_back(i);
    } else {
      rp.push_back(i);
    }
  }
  n = lp.size() + rp.size() + 2;
  s = 0;
  t = n - 1;
  g.assign(n, vector<int>());
  e.clear();
  int sum = 0;
  for (int i = 0; i < lp.size(); i++) {
    add_edge(s, i + 1, cards[lp[i]].pwr);
    sum += cards[lp[i]].pwr;
    for (int j = 0; j < rp.size(); j++) {
      if (prime[cards[lp[i]].num + cards[rp[j]].num]) {
        add_edge(i + 1, 1 + lp.size() + j, inf);
      }
    }
  }
  for (int j = 0; j < rp.size(); j++) {
    add_edge(1 + lp.size() + j, t, cards[rp[j]].pwr);
    sum += cards[rp[j]].pwr;
  }
  int res = mincut();
  res = sum - res;
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int kek, k;
  cin >> kek >> k;
  int pwr, num, lev;
  for (int i = 0; i < kek; i++) {
    cin >> pwr >> num >> lev;
    cards.push_back(card{pwr, num, lev});
  }
  kek = 200005;
  prime.assign(kek, true);
  for (int i = 2; i < kek; i++) {
    if (!prime[i]) continue;
    for (long long j = i * 1ll * i; j < kek; j += i) {
      prime[j] = false;
    }
  }
  int l = 1;
  int r = 101;
  while (l < r) {
    int mid = (l + r) / 2;
    pwr = max_pow(mid);
    if (pwr < k) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  if (l == 101) {
    cout << -1;
  } else {
    cout << l;
  }
}
