#include <bits/stdc++.h>
using namespace std;
int n, k, p[111], c[111], l[111], bottleneck[111], par[111], cost[111][111];
bitset<200005> prime;
vector<vector<int> > vert;
int edmondskarp(int s, int t) {
  int mf = 0;
  while (1) {
    memset(bottleneck, 0, sizeof(bottleneck));
    bottleneck[s] = 1e9;
    par[s] = s;
    queue<int> q;
    q.push(s);
    while (!q.empty() && !bottleneck[t]) {
      int u = q.front();
      q.pop();
      for (int i = 0; i < vert[u].size(); i++) {
        int v = vert[u][i];
        if (cost[u][v] > 0 && !bottleneck[v]) {
          q.push(v);
          par[v] = u;
          bottleneck[v] = min(bottleneck[u], cost[u][v]);
        }
      }
    }
    if (!bottleneck[t]) break;
    mf += bottleneck[t];
    for (int u = t; par[u] != u; u = par[u]) {
      cost[par[u]][u] -= bottleneck[t];
      cost[u][par[u]] += bottleneck[t];
    }
  }
  return mf;
}
int ok(int x) {
  int idx = 0;
  p[0] = -1;
  for (int i = 1; i <= n; i++) {
    if (c[i] == 1 && l[i] <= x && p[i] > p[idx]) {
      idx = i;
    }
  }
  vert.assign(111, vector<int>());
  memset(cost, 0, sizeof(cost));
  for (int i = 1; i <= n; i++) {
    if (l[i] > x) continue;
    if (c[i] & 1) continue;
    if (c[i] == 1) continue;
    for (int j = 1; j <= n; j++) {
      if (l[j] > x) continue;
      if (i == j) continue;
      if (c[j] == 1) continue;
      if (prime[c[i] + c[j]]) {
        vert[i].push_back(j);
        vert[j].push_back(i);
        cost[i][j] = 1e9;
      }
    }
  }
  int s = 101, t = 102;
  for (int i = 1; i <= n; i++) {
    if (l[i] > x) continue;
    if (c[i] & 1) continue;
    if (c[i] == 1) continue;
    vert[s].push_back(i);
    vert[i].push_back(s);
    cost[s][i] = p[i];
  }
  for (int i = 1; i <= n; i++) {
    if (l[i] > x) continue;
    if (!(c[i] & 1)) continue;
    if (c[i] == 1) continue;
    vert[i].push_back(t);
    vert[t].push_back(i);
    cost[i][t] = p[i];
  }
  if (idx) {
    vert[idx].push_back(t);
    vert[t].push_back(idx);
    cost[idx][t] = p[idx];
    for (int i = 1; i <= n; i++) {
      if (l[i] > x) continue;
      if (c[i] & 1) continue;
      if (!prime[1 + c[i]]) continue;
      vert[i].push_back(idx);
      vert[idx].push_back(i);
      cost[i][idx] = 1e9;
    }
  }
  int sum = 0;
  for (int i = 1; i <= n; i++) {
    if (l[i] > x || c[i] == 1) continue;
    sum += p[i];
  }
  if (idx) sum += p[idx];
  int ek = edmondskarp(s, t);
  return sum - ek >= k;
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &p[i], &c[i], &l[i]);
  }
  prime.set();
  prime[0] = prime[1] = 0;
  for (long long i = 2; i <= 200000; i++) {
    if (prime[i]) {
      for (long long j = i * i; j <= 200000; j += i) {
        prime[j] = 0;
      }
    }
  }
  if (!ok(n)) {
    printf("%d\n", -1);
    return 0;
  }
  int lo = 0, hi = n;
  while (hi - lo > 1) {
    int m = (lo + hi) / 2;
    if (ok(m))
      hi = m;
    else
      lo = m;
  }
  printf("%d\n", hi);
  return 0;
}
