#include <bits/stdc++.h>
using namespace std;
const int N = 620, M = 1000005, LINF = 0x3fffffff;
struct MaxFlow {
  int n, et, dis[N], que[N], cur[N], head[N];
  struct Edge {
    int s, t, v, nxt;
    Edge() {}
    Edge(int _s, int _t, int _v, int _nxt) {
      s = _s, t = _t, v = _v, nxt = _nxt;
    }
  } e[M * 2], b[M * 2];
  void undo() {
    for (int i = 0; i < et; i++) e[i] = b[i];
  }
  void backup() {
    for (int i = 0; i < et; i++) b[i] = e[i];
  }
  void init(int _n) {
    n = _n, et = 0;
    memset(head, -1, sizeof(head[0]) * n);
  }
  void addEdge(int s, int t, int v) {
    e[et] = Edge(s, t, v, head[s]), head[s] = et++;
    e[et] = Edge(t, s, 0, head[t]), head[t] = et++;
  }
  bool bfs(int S, int T) {
    int qh = 0, qt = 0;
    memset(dis, -1, sizeof(dis[0]) * n);
    dis[S] = 0, que[qt++] = S;
    while (qh < qt)
      for (int i = head[que[qh++]]; ~i; i = e[i].nxt)
        if (e[i].v && !~dis[e[i].t]) {
          dis[que[qt++] = e[i].t] = 1 + dis[e[i].s];
          if (e[i].t == T) return true;
        }
    return false;
  }
  long long dinic(int S, int T) {
    int u, qt;
    long long maxflow = 0;
    while (bfs(S, T)) {
      memcpy(cur, head, sizeof(cur[0]) * n);
      u = S, qt = 0;
      while (~cur[S]) {
        if (u == T) {
          long long flow = LINF;
          for (int i = qt - 1; i >= 0; --i)
            flow = min(flow, (long long)e[que[i]].v);
          for (int i = qt - 1; i >= 0; --i) {
            e[que[i]].v -= flow, e[que[i] ^ 1].v += flow;
            if (!e[que[i]].v) qt = i;
          }
          u = e[que[qt]].s, maxflow += flow;
        } else if (~cur[u] && e[cur[u]].v && dis[u] + 1 == dis[e[cur[u]].t]) {
          que[qt++] = cur[u];
          u = e[cur[u]].t;
        } else {
          while (u != S && !~cur[u]) u = e[que[--qt]].s;
          cur[u] = e[cur[u]].nxt;
        }
      }
    }
    return maxflow;
  }
} G;
int a[105], b[105], c[105];
int noprime[200005], prime[200005], p = 0;
int main() {
  for (int i = 2; i < 200005; i++) {
    if (!noprime[i]) prime[++p] = i;
    for (int j = 1; j <= p, i * prime[j] < 200005; j++) {
      noprime[i * prime[j]] = 1;
      if (!(i % prime[j])) break;
    }
  }
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = (1); i < (n + 1); ++i) scanf("%d%d%d", &a[i], &b[i], &c[i]);
  int l = 1, r = n + 1;
  while (l < r) {
    G.init(400);
    int mid = (l + r) >> 1;
    vector<int> id[2];
    id[1].push_back(0);
    for (int i = (1); i < (n + 1); ++i)
      if (c[i] <= mid) {
        if (b[i] == 1) {
          if (a[id[1][0]] < a[i]) id[1][0] = i;
        } else
          id[b[i] & 1].push_back(i);
      }
    for (int i = (0); i < (((int)(id[0]).size())); ++i)
      G.addEdge(0, i + 1, a[id[0][i]]);
    int id1 = 0;
    for (int i = (!id[1][0]); i < (((int)(id[1]).size())); ++i)
      G.addEdge(100 + i + 1, 301, a[id[1][i]]);
    for (int i = (0); i < (((int)(id[0]).size())); ++i)
      for (int j = (!id[1][0]); j < (((int)(id[1]).size())); ++j)
        if (!noprime[b[id[0][i]] + b[id[1][j]]])
          G.addEdge(i + 1, 100 + j + 1, LINF);
    long long ans = 0;
    for (int i = (0); i < (2); ++i)
      for (int j = (0); j < (((int)(id[i]).size())); ++j) ans += a[id[i][j]];
    ans -= G.dinic(0, 301);
    if (ans < k)
      l = mid + 1;
    else
      r = mid;
  }
  if (l == n + 1)
    cout << -1 << endl;
  else
    cout << l << endl;
  return 0;
}
