#include <bits/stdc++.h>
using namespace std;
int cnt, head[110], dis[110], vis[110];
struct Edge {
  int to, nxt, f;
} e[(110 * 110) << 2];
int t, n, k, ss, tt;
bool np[200007] = {1, 1};
struct pos {
  int p, c, l;
} ps[110];
void adde(int u, int v, int c) {
  e[++cnt].to = v;
  e[cnt].f = c;
  e[cnt].nxt = head[u];
  head[u] = cnt;
  e[++cnt].to = u;
  e[cnt].f = 0;
  e[cnt].nxt = head[v];
  head[v] = cnt;
}
bool bfs() {
  memset(dis, 0, sizeof(dis));
  memset(vis, 0, sizeof(vis));
  queue<int> q;
  vis[ss] = 1;
  q.push(ss);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; ~i; i = e[i].nxt) {
      int v = e[i].to;
      if (e[i].f && !vis[v]) {
        q.push(v);
        vis[v] = 1;
        dis[v] = dis[u] + 1;
      }
    }
  }
  return vis[tt];
}
int dfs(int u, int delta) {
  if (u == tt) return delta;
  int ret = 0;
  for (int i = head[u]; delta && ~i; i = e[i].nxt) {
    int v = e[i].to;
    if (e[i].f && dis[v] == dis[u] + 1) {
      int flow = dfs(v, min(e[i].f, delta));
      e[i].f -= flow;
      e[i ^ 1].f += flow;
      delta -= flow;
      ret += flow;
    }
  }
  return ret;
}
int Dinic() {
  int ret = 0;
  while (bfs()) ret += dfs(ss, 0x3f3f3f3f);
  return ret;
}
bool check(int M) {
  cnt = -1;
  memset(head, -1, sizeof(head));
  int m1 = -1, w1 = -1;
  for (int i = 1; i <= n; ++i) {
    if (ps[i].l <= M) {
      if (ps[i].c == 1 && ps[i].p > m1) m1 = ps[i].p, w1 = i;
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i)
    if (ps[i].l <= M) {
      if (ps[i].c == 1 && i != w1) continue;
      ans += ps[i].p;
      if (ps[i].c & 1) {
        adde(ss, i, ps[i].p);
        for (int j = 1; j <= n; ++j)
          if (ps[j].l <= M && (~ps[j].c & 1) && !np[ps[i].c + ps[j].c]) {
            adde(i, j, 0x3f3f3f3f);
          }
      } else
        adde(i, tt, ps[i].p);
    }
  ans -= Dinic();
  return ans < k;
}
int main() {
  for (int i = 2; i <= 200000; ++i)
    if (!np[i])
      for (int j = i * 2; j <= 200000; j += i) np[j] = 1;
  scanf("%d%d", &n, &k);
  ss = n + 1, tt = n + 2;
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d%d", &ps[i].p, &ps[i].c, &ps[i].l);
  }
  int L = 1, R = n + 1, M;
  while (L < R) {
    M = L + R >> 1;
    if (check(M))
      L = M + 1;
    else
      R = M;
  }
  printf("%d", L > n ? -1 : L);
  return 0;
}
