#include <bits/stdc++.h>
#pragma GCC optimize("-Ofast", "-funroll-all-loops")
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 110, M = 1e6 + 10;
int n, k, p[N], c[N], l[N], h[N], s, t, mx, flag, res;
int head[N], nex[M], to[M], w[M], tot;
inline void ade(int a, int b, int c) {
  to[++tot] = b;
  nex[tot] = head[a];
  w[tot] = c;
  head[a] = tot;
}
inline void add(int a, int b, int c) {
  ade(a, b, c);
  ade(b, a, 0);
}
inline int isprime(int x) {
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
inline int bfs() {
  queue<int> q;
  q.push(s);
  memset(h, 0, sizeof h);
  h[s] = 1;
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = nex[i]) {
      if (w[i] && !h[to[i]]) {
        h[to[i]] = h[u] + 1;
        q.push(to[i]);
      }
    }
  }
  return h[t];
}
int dfs(int x, int f) {
  if (x == t) return f;
  int fl = 0;
  for (int i = head[x]; i; i = nex[i]) {
    if (w[i] && h[to[i]] == h[x] + 1) {
      int mi = dfs(to[i], min(w[i], f));
      w[i] -= mi, w[i ^ 1] += mi, fl += mi, f -= mi;
    }
  }
  if (!fl) h[x] = -1;
  return fl;
}
inline int dinic() {
  int res = 0;
  while (bfs()) res += dfs(s, inf);
  return res;
}
inline int check(int mid) {
  tot = 1;
  memset(head, 0, sizeof head);
  mx = flag = res = 0;
  for (int i = 1; i <= n; i++)
    if (l[i] <= mid) {
      if (c[i] == 1) mx = max(mx, p[i]);
    }
  for (int i = 1; i <= n; i++)
    if (l[i] <= mid) {
      if (c[i] & 1) {
        if (c[i] == 1) {
          if (!flag && p[i] == mx) add(s, i, p[i]), flag = 1, res += p[i];
        } else
          add(s, i, p[i]), res += p[i];
      } else
        add(i, t, p[i]), res += p[i];
    }
  for (int i = 1; i <= n; i++)
    if (c[i] % 2 && l[i] <= mid) {
      for (int j = 1; j <= n; j++)
        if (c[j] % 2 == 0 && l[j] <= mid) {
          if (isprime(c[i] + c[j])) add(i, j, inf);
        }
    }
  return res - dinic() >= k;
}
signed main() {
  cin >> n >> k;
  t = n + 1;
  for (int i = 1; i <= n; i++) cin >> p[i] >> c[i] >> l[i];
  int L = 1, R = n + 1;
  while (L < R) {
    int mid = L + R >> 1;
    if (check(mid))
      R = mid;
    else
      L = mid + 1;
  }
  if (L == n + 1) L = -1;
  cout << L;
  return 0;
}
