#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
bool m[N];
void sieve() {
  for (int i = 4; i < N; i += 2) m[i] = 1;
  for (int i = 3; i * i < N; i += 2)
    if (!m[i])
      for (int j = i * i; j < N; j += i) m[j] = 1;
}
const long long INF = 1e14;
struct Dinic {
  int nodes, src, dst;
  vector<int> dist, q, work;
  struct edge {
    int to, rev;
    long long first, cap;
  };
  vector<vector<edge>> g;
  Dinic(int x) : nodes(x), g(x), dist(x), q(x), work(x) {}
  void add(int second, int t, long long cap) {
    g[second].push_back((edge){t, int(g[t].size()), 0, cap});
    g[t].push_back((edge){second, int(g[second].size()) - 1, 0, 0});
  }
  bool bfs() {
    fill(begin(dist), end(dist), -1);
    dist[src] = 0;
    int qt = 0;
    q[qt++] = src;
    for (int qh = 0; qh < qt; qh++) {
      int u = q[qh];
      for (int i = (0), ThxMK = (int(g[u].size())); i < ThxMK; ++i) {
        edge &e = g[u][i];
        int v = g[u][i].to;
        if (dist[v] < 0 && e.first < e.cap) dist[v] = dist[u] + 1, q[qt++] = v;
      }
    }
    return dist[dst] >= 0;
  }
  long long dfs(int u, long long first) {
    if (u == dst) return first;
    for (int &i = work[u]; i < int(g[u].size()); i++) {
      edge &e = g[u][i];
      if (e.cap <= e.first) continue;
      int v = e.to;
      if (dist[v] == dist[u] + 1) {
        long long df = dfs(v, min(first, e.cap - e.first));
        if (df > 0) {
          e.first += df;
          g[v][e.rev].first -= df;
          return df;
        }
      }
    }
    return 0;
  }
  long long max_flow(int _src, int _dst) {
    src = _src;
    dst = _dst;
    long long result = 0;
    while (bfs()) {
      fill(begin(work), end(work), 0);
      while (long long delta = dfs(src, INF)) result += delta;
    }
    return result;
  }
};
long long n, k;
vector<pair<long long, pair<int, int>>> par, impar, unos;
bool calc(int u) {
  int mm = 0, ix = 0;
  for (int i = (0), ThxMK = (int(unos.size())); i < ThxMK; ++i) {
    if (u < unos[i].first) break;
    if (unos[i].second.first > mm) {
      mm = unos[i].second.first;
      ix = i;
    }
  }
  if (mm) impar.push_back(unos[ix]);
  sort(begin(impar), end(impar));
  int T = int(par.size()) + int(impar.size()) + 5;
  Dinic D(T);
  for (int i = (0), ThxMK = (int(par.size())); i < ThxMK; ++i) {
    if (u < par[i].first) break;
    for (int j = (0), ThxMK = (int(impar.size())); j < ThxMK; ++j) {
      if (u < impar[j].first) break;
      if (!m[par[i].second.second + impar[j].second.second])
        D.add(i, int(par.size()) + j, INF);
    }
  }
  long long sum = 0;
  for (int i = (0), ThxMK = (int(par.size())); i < ThxMK; ++i) {
    if (u < par[i].first) break;
    D.add(T - 2, i, par[i].second.first);
    sum += par[i].second.first;
  }
  for (int i = (0), ThxMK = (int(impar.size())); i < ThxMK; ++i) {
    if (u < impar[i].first) break;
    D.add(int(par.size()) + i, T - 1, impar[i].second.first);
    sum += impar[i].second.first;
  }
  long long res = D.max_flow(T - 2, T - 1);
  for (int i = (0), ThxMK = (int(impar.size())); i < ThxMK; ++i)
    if (impar[i].second.second == 1) impar[i].first = N + 5;
  return sum - res >= k;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  sieve();
  for (int i = (0), ThxMK = (n); i < ThxMK; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    if (b == 1) {
      unos.push_back({c, {a, b}});
      continue;
    }
    if (b & 1)
      impar.push_back({c, {a, b}});
    else
      par.push_back({c, {a, b}});
  }
  sort(begin(par), end(par));
  sort(begin(unos), end(unos));
  int l = 0, r = n, last = r + 1;
  while (l <= r) {
    int mid = (l + r) / 2;
    bool ok = calc(mid);
    if (ok) {
      r = mid - 1;
      last = mid;
    } else
      l = mid + 1;
  }
  if (last > n)
    cout << -1 << '\n';
  else
    cout << last << '\n';
}
