#include <bits/stdc++.h>
using namespace std;
void ga(int N, int *A) {
  for (int i(0); i < N; i++) scanf("%d", A + i);
}
long long P[(1 << 14) >> 1] = {2}, L(1), cn[1 + ((1 << 14) >> 6)];
void gen() {
  (cn[0 >> 6] |= 1ULL << ((0 & 63))), (cn[1 >> 6] |= 1ULL << ((1 & 63)));
  int Q(1 + sqrt((1 << 14)));
  for (long long i(4); i < (1 << 14); i += 2)
    (cn[i >> 6] |= 1ULL << ((i & 63)));
  for (int k(3); k <= Q; k += 2)
    if (!((cn[k >> 6] >> (k & 63)) & 1))
      for (long long h(k << 1), j(k * k); j < (1 << 14); j += h)
        (cn[j >> 6] |= 1ULL << ((j & 63)));
  for (int i(3); i < (1 << 14); i += 2)
    if (!((cn[i >> 6] >> (i & 63)) & 1)) P[L++] = i;
}
int N, K, A[512], B[512], Z[512], z[512];
struct Dinic {
  int n, m, h[512], l[512], s, t, w[512];
  struct eg {
    int v, c, f, x;
  } e[(1 << 14)];
  bool bfs() {
    static int q[512];
    for (int i(0); i < n; i++) l[i] = -1;
    int B(l[s] = 0), E(1);
    q[0] = s;
    while (B < E)
      for (int k(q[B++]), i(h[k]); ~i; i = e[i].x)
        if (e[i].f < e[i].c && !~l[e[i].v])
          l[e[i].v] = l[k] + 1, q[E++] = e[i].v;
    return ~l[t];
  }
  int dfs(int u, int f) {
    if (u == t) return f;
    int mf;
    for (int i(w[u]); ~i; i = e[i].x)
      if (e[i].f < e[i].c && l[u] + 1 == l[e[i].v])
        if ((mf = dfs(e[i].v, min(f, e[i].c - e[i].f))) > 0)
          return e[i].f += mf, e[i ^ 1].f -= mf, mf;
    return 0;
  }
  void ini(int N, int f, int d) {
    n = N;
    s = f;
    t = d;
    m = 0;
    for (int i(0); i < n; i++) h[i] = -1;
  }
  void ade(int u, int v, int c = 1, int rc = 0) {
    e[m] = eg{v, c, 0, h[u]};
    h[u] = m++;
    e[m] = eg{u, rc, 0, h[v]};
    h[v] = m++;
  }
  int mf() {
    int a(0), d;
    while (bfs()) {
      memcpy(w, h, sizeof(int) * n);
      do a += d = dfs(s, int(1e9 + 1));
      while (d);
    }
    return a;
  }
} H;
bool ok(long long t) {
  if (t > N) return 1;
  long long S = 0, o = -1, p = -1;
  (memset(z, 0, sizeof(z)));
  for (int i(0); i < N; i++)
    if (Z[i] <= t) {
      if (B[i] == 1) {
        if (A[i] > p) p = A[i], o = i;
      } else
        z[i] = 1, S += A[i];
    }
  if (~o) z[o] = 1, S += p;
  H.ini(N + 2, N, N + 1);
  for (int i(0); i < N; i++)
    if (z[i] && B[i] & 1) H.ade(N, i, A[i]);
  for (int i(0); i < N; i++)
    if (z[i] && !(B[i] & 1)) H.ade(i, N + 1, A[i]);
  for (int i(0); i < N; i++)
    if (z[i] && B[i] & 1)
      for (int j(0); j < N; j++)
        if (z[j] && !(B[j] & 1) &&
            !((cn[(B[i] + B[j]) >> 6] >> ((B[i] + B[j]) & 63)) & 1))
          H.ade(i, j, 1024);
  return S - H.mf() >= K;
}
long long bs(long long B = 0, long long E = int(1e9 + 1)) {
  long long M;
  while (B < E)
    if (ok(M = (B + E) >> 1))
      E = M;
    else
      B = M + 1;
  if (B > N) return -1;
  return B;
}
int main(void) {
  scanf("%d%d", &N, &K), gen();
  for (int i(0); i < N; i++) scanf("%d%d%d", A + i, B + i, Z + i);
  printf("%lld\n", bs(0, N + 2));
  return 0;
}
