#include <bits/stdc++.h>
using namespace std;
static const int INF = 0x3FFFFFFF;
struct Dinic {
  struct Edge {
    int t, c, r;
  };
  void add(int u, int v, int c) {
    E[u].push_back({v, c, (int)E[v].size()});
    E[v].push_back({u, 0, (int)E[u].size() - 1});
  }
  int n;
  vector<int> D;
  vector<vector<Edge>> E;
  Dinic(int _n) : n(_n), E(_n) {}
  bool bfs() {
    D.assign(n, INF);
    D[0] = 0;
    queue<int> Q;
    for (Q.push(0); !Q.empty(); Q.pop()) {
      int u = Q.front();
      for (Edge &e : E[u])
        if (e.c > 0 && D[e.t] == INF) {
          D[e.t] = D[u] + 1;
          Q.push(e.t);
        }
    }
    return D[n - 1] < INF;
  }
  int dfs(int u, int rem) {
    int res = 0;
    if (u == n - 1 || rem == 0) return rem;
    for (Edge &e : E[u])
      if (D[e.t] == D[u] + 1) {
        int t = dfs(e.t, min(rem, e.c));
        res += t;
        rem -= t;
        e.c -= t;
        E[e.t][e.r].c += t;
      }
    if (res == 0) D[u] = -1;
    return res;
  }
  int sol() {
    int res = 0, tmp;
    while (bfs())
      while ((tmp = dfs(0, INF))) res += tmp;
    return res;
  }
};
bool isPrime(int x) {
  static const int N = 300000;
  static vector<bool> isp(N, true);
  if (isp[1]) {
    isp[1] = false;
    for (int i = 2; i < N; i++)
      if (isp[i])
        for (long long j = (long long)i * i; j < N; j += i) isp[(int)j] = false;
  }
  return isp[x];
}
bool check(int m, int n, int k, vector<vector<int>> v) {
  for (int i = 0; i < n; i++)
    if (v[i][2] > m) swap(v[i], v.back()), v.pop_back(), i--, n--;
  for (int i = 0, prei = -1; i < n; i++)
    if (v[i][1] == 1) {
      if (prei == -1)
        prei = i;
      else {
        if (v[prei][0] < v[i][0]) swap(v[prei], v[i]);
        swap(v[i], v.back()), v.pop_back(), i--, n--;
      }
    }
  vector<vector<int>> E(n);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (i != j && isPrime(v[i][1] + v[j][1])) E[i].push_back(j);
  Dinic dinic(n + 2);
  for (int i = 0; i < n; i++)
    if (v[i][1] % 2)
      dinic.add(i + 1, n + 1, v[i][0]);
    else
      dinic.add(0, i + 1, v[i][0]);
  for (int i = 0; i < n; i++)
    if (v[i][1] % 2 == 0)
      for (int x : E[i]) dinic.add(i + 1, x + 1, INF);
  int sum = 0;
  for (int i = 0; i < n; i++) sum += v[i][0];
  return sum - dinic.sol() >= k;
}
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  vector<vector<int>> v(n, {0, 0, 0});
  for (int i = 0; i < n; i++) scanf("%d%d%d", &v[i][0], &v[i][1], &v[i][2]);
  int ans = -1;
  for (int l = 1, r = n + 1; l < r;) {
    int m = (l + r) / 2;
    if (check(m, n, k, v))
      ans = r = m;
    else
      l = m + 1;
  }
  printf("%d\n", ans);
}
