#include <bits/stdc++.h>
using namespace std;
long long n, k, ep = 0, from[1000100], to[1000100], cap[1000100], INF = 1e18;
vector<long long> gr[1100];
bool erath[211000], visited[1000100], logger;
bool is_erath_com = false;
bool isPrime(long long x) {
  if (!is_erath_com) {
    is_erath_com = true;
    for (long long i = 2; i < 211000; i++) erath[i] = true;
    for (long long i = 2; i < 211000; i++)
      if (erath[i])
        for (long long j = 2 * i; j < 211000; j += i) erath[j] = false;
  }
  if (logger) cerr << "isprime" << x << " " << erath[x] << "\n";
  return erath[x];
}
struct Card {
  long long p, c, l;
} cards[1100];
long long dfs(long long source, long long sink, long long f) {
  if (source == sink) {
    return f;
  }
  long long tot = 0;
  for (long long e : gr[source]) {
    if (f && !visited[e] && cap[e]) {
      visited[e] = true;
      long long nb_flow = dfs(to[e], sink, min(f, cap[e]));
      cap[e] -= nb_flow;
      cap[e ^ 1] += nb_flow;
      tot += nb_flow;
      f -= nb_flow;
    }
  }
  return tot;
}
long long compute_flow() {
  long long source = 0, sink = n + 1, flow = 0, add = 0;
  do {
    flow += add;
    for (long long i = 0; i < ep; i++) visited[i] = false;
  } while (add = dfs(source, sink, INF));
  return flow;
}
void add_edge(long long u, long long v, long long p) {
  if (logger) cerr << "add edge " << u << " " << v << " " << p << "\n";
  from[ep] = u;
  to[ep] = v;
  cap[ep] = p;
  gr[u].push_back(ep);
  ep++;
  from[ep] = v;
  to[ep] = u;
  cap[ep] = 0;
  gr[v].push_back(ep);
  ep++;
}
void remove_all_edges() {
  ep = 0;
  for (long long i = 0; i <= n + 1; i++) gr[i].clear();
}
long long isGood(long long level) {
  logger = level == 1;
  long long m1power = 0, tot_p = 0, m1_ind = 0;
  remove_all_edges();
  for (long long i = 1; i <= n; i++) {
    if (cards[i].l > level) continue;
    if (cards[i].c % 2) {
      if (cards[i].c == 1) {
        if (cards[i].p > m1power) {
          m1power = cards[i].p;
          m1_ind = i;
        }
        continue;
      }
      add_edge(0, i, cards[i].p);
      tot_p += cards[i].p;
    } else {
      add_edge(i, n + 1, cards[i].p);
      tot_p += cards[i].p;
      for (long long j = 1; j <= n; j++)
        if (isPrime(cards[i].c + cards[j].c)) add_edge(j, i, INF);
    }
  }
  if (m1_ind) add_edge(0, m1_ind, m1power);
  tot_p += m1power;
  long long flow = compute_flow();
  if (logger) cerr << "\n";
  if (logger) cerr << level << " " << tot_p << " " << flow << "\n";
  return tot_p - flow >= k;
}
int main() {
  scanf("%I64d %I64d", &n, &k);
  for (long long i = 1; i <= n; i++)
    scanf("%I64d %I64d %I64d", &cards[i].p, &cards[i].c, &cards[i].l);
  long long bad = 0, good = 1001;
  while (good - bad > 1) {
    long long m = good + bad >> 1;
    if (isGood(m))
      good = m;
    else
      bad = m;
  }
  if (good == 1001)
    printf("-1");
  else
    printf("%I64d", good);
  return 0;
}
