#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e2 + 10;
const int MAXM = 3e4 + 10;
const int MAXX = 2e5 + 10;
const int inf = 1e9;
int pcnt;
int p[MAXX];
bool isnp[MAXX];
inline void init(int n) {
  isnp[0] = isnp[1] = true;
  for (int i = 2; i <= n; i++) {
    if (!isnp[i]) p[++pcnt] = i;
    for (int j = 1; j <= pcnt && (long long)i * p[j] <= n; j++) {
      isnp[i * p[j]] = true;
      if (i % p[j] == 0) break;
    }
  }
}
int n, kkk;
int pw[MAXN];
int mgc[MAXN];
int lv[MAXN];
struct Edge {
  int to, nxt, w;
};
int cnt_e, S, T;
int head[MAXN], curh[MAXN];
int deep[MAXN];
Edge e[MAXM];
inline void addedge(int u, int v, int w) {
  e[++cnt_e].to = v;
  e[cnt_e].w = w;
  e[cnt_e].nxt = head[u];
  head[u] = cnt_e;
}
inline bool bfs() {
  for (int i = 1; i <= n + 2; i++) curh[i] = head[i];
  for (int i = 1; i <= n + 2; i++) deep[i] = -1;
  queue<int> q;
  q.push(S);
  deep[S] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = e[i].nxt) {
      int v = e[i].to, w = e[i].w;
      if (deep[v] != -1 || !w) continue;
      deep[v] = deep[u] + 1;
      q.push(v);
      if (v == T) return true;
    }
  }
  return false;
}
inline int dfs(int u, int flow) {
  if (u == T || !flow) return flow;
  int res = 0;
  for (int &i = curh[u]; i; i = e[i].nxt) {
    int v = e[i].to, w = e[i].w;
    if (deep[v] != deep[u] + 1 || !w) continue;
    int k = dfs(v, min(flow, w));
    flow -= k;
    res += k;
    e[i].w -= k;
    e[i ^ 1].w += k;
    if (!flow) break;
  }
  return res;
}
inline int dinic() {
  int res = 0;
  while (bfs()) res += dfs(S, 1e9);
  return res;
}
inline bool chk(int mid) {
  int Mx = 0, pos = -1;
  for (int i = 1; i <= n; i++)
    if (lv[i] <= mid && mgc[i] == 1 && Mx < pw[i]) Mx = pw[i], pos = i;
  int res = Mx;
  for (int i = 1; i <= n; i++)
    if (lv[i] <= mid && mgc[i] > 1) res += pw[i];
  cnt_e = 1;
  memset(head, 0, sizeof(head));
  S = n + 1, T = n + 2;
  for (int i = 1; i <= n; i++) {
    if (lv[i] > mid) continue;
    if (!(mgc[i] & 1)) continue;
    if (mgc[i] == 1 && i != pos) continue;
    addedge(S, i, pw[i]), addedge(i, S, 0);
    for (int j = 1; j <= n; j++) {
      if (lv[j] > mid) continue;
      if (mgc[j] & 1) continue;
      if (isnp[mgc[i] + mgc[j]]) continue;
      addedge(i, j, inf);
      addedge(j, i, 0);
    }
  }
  for (int i = 1; i <= n; i++) {
    if (lv[i] > mid) continue;
    if (mgc[i] & 1) continue;
    addedge(i, T, pw[i]);
    addedge(T, i, 0);
  }
  int cao = dinic();
  return res - cao >= kkk;
}
int main() {
  init(2e5);
  scanf("%d%d", &n, &kkk);
  for (int i = 1; i <= n; i++) scanf("%d%d%d", &pw[i], &mgc[i], &lv[i]);
  int l = 1, r = n;
  int ans = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (chk(mid))
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%d\n", ans);
  return 0;
}
