#include <bits/stdc++.h>
using namespace std;
const int INFCAP = 1000000005;
const int MAXN = 205;
typedef struct {
  int to;
  int cap;
} edge;
vector<int> ai[MAXN];
vector<edge> el;
int lev[MAXN];
int SRC;
int DST;
vector<int> lai[MAXN];
unsigned ng[MAXN];
int path[MAXN];
int pathsz;
void addedge(int u, int v, int c) {
  const int idx = el.size();
  const edge e1 = {v, c}, e2 = {u, 0};
  ai[u].push_back(idx);
  el.push_back(e1);
  ai[v].push_back(idx + 1);
  el.push_back(e2);
}
bool buildlevel() {
  for (int i = 0; i < MAXN; i++) lai[i].clear();
  fill(lev, lev + MAXN, 0);
  queue<int> q;
  q.push(SRC);
  lev[SRC] = 1;
  while (!q.empty()) {
    const int v = q.front();
    q.pop();
    if (v == DST) return true;
    for (auto idx : ai[v]) {
      const edge& e = el[idx];
      if (e.cap > 0) {
        if (lev[e.to] == 0) {
          lev[e.to] = lev[v] + 1;
          lai[v].push_back(idx);
          q.push(e.to);
        } else if (lev[e.to] == lev[v] + 1) {
          lai[v].push_back(idx);
        }
      }
    }
  }
  return false;
}
int dfs(int v) {
  if (v == DST) return INFCAP;
  for (; ng[v] < lai[v].size(); ng[v]++) {
    const edge& e = el[lai[v][ng[v]]];
    if (e.cap > 0) {
      int fl = dfs(e.to);
      if (fl > 0) {
        path[pathsz++] = lai[v][ng[v]];
        return min(fl, e.cap);
      }
    }
  }
  return 0;
}
void resetflow() {
  for (int i = 0; i < MAXN; i++) ai[i].clear();
  el.clear();
}
long long maxflow(int src, int dst) {
  SRC = src, DST = dst;
  long long ret = 0;
  while (buildlevel()) {
    fill(ng, ng + MAXN, 0);
    int fl;
    while ((fl = dfs(SRC)) > 0) {
      ret += fl;
      for (int i = 0; i < pathsz; i++) {
        el[path[i]].cap -= fl;
        el[path[i] ^ 1].cap += fl;
      }
      pathsz = 0;
    }
  }
  return ret;
}
vector<int> ones;
vector<int> par[2];
int cards[102][3];
const int MAXV = 200002;
bool sieve[MAXV];
int side[2][102];
int ssz[2];
long long n, k;
void fillsieve() {
  sieve[0] = sieve[1] = false;
  sieve[2] = true;
  for (long long i = 3; i < MAXV; i += 2) sieve[i] = true;
  for (long long i = 3; i < MAXV; i++)
    if (sieve[i])
      for (long long j = i * i; j < MAXV; j += 2 * i) sieve[j] = false;
}
bool go(int lev) {
  resetflow();
  ssz[0] = ssz[1] = 0;
  long long mwo = -1;
  long long totwt = 0;
  for (int i = 0; i < (int)ones.size(); i++)
    if (cards[ones[i]][2] <= lev && cards[ones[i]][0] > mwo)
      mwo = cards[ones[i]][0];
  if (mwo > 0) {
    side[1][ssz[1]] = -1;
    addedge(100 + ssz[1], DST, mwo);
    ssz[1]++;
    totwt += mwo;
  }
  for (int i = 0; i < 2; i++)
    for (auto it : par[i])
      if (cards[it][2] <= lev) {
        side[i][ssz[i]] = it;
        if (i)
          addedge(100 + ssz[i], DST, cards[it][0]);
        else
          addedge(SRC, ssz[i], cards[it][0]);
        totwt += cards[it][0];
        ssz[i]++;
      }
  for (int i = 0; i < ssz[0]; i++) {
    const int e = cards[side[0][i]][1];
    for (int j = 0; j < ssz[1]; j++) {
      const int o = side[1][j] < 0 ? 1 : cards[side[1][j]][1];
      if (sieve[e + o]) addedge(i, 100 + j, INFCAP);
    }
  }
  return totwt - maxflow(SRC, DST) >= k;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  fillsieve(), SRC = 203, DST = 204;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 3; j++) cin >> cards[i][j];
    if (cards[i][1] == 1)
      ones.push_back(i);
    else
      par[cards[i][1] % 2].push_back(i);
  }
  int lo = 1;
  int hi = n + 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (go(mid))
      hi = mid;
    else
      lo = mid + 1;
  }
  cout << (lo == n + 1 ? -1 : lo) << endl;
  return 0;
}
