#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, m, cnt = 1, l = 0x7fffffff, r, ans = -1, S, T, sum;
int b[20205], p[105], nextedge[20205], w[20205], cur[105];
int Level[105];
int prime[100005];
bool Not_Prime[100005] = {1, 1};
void Get_Prime() {
  for (int i = 2; i < 100005; i++) {
    if (!Not_Prime[i]) prime[++prime[0]] = i;
    for (int j = 1; j <= prime[0] && i * prime[j] < 100005; j++) {
      Not_Prime[i * prime[j]] = 1;
      if ((i % prime[j]) == 0) break;
    }
  }
}
class Card {
 public:
  int p, c, l;
} e[105];
void Add(int x, int y, int z) {
  cnt++;
  b[cnt] = y;
  nextedge[cnt] = p[x];
  p[x] = cnt;
  w[cnt] = z;
}
void Anode(int x, int y, int z) {
  Add(x, y, z);
  Add(y, x, 0);
}
void Build1(int mid) {
  memset(p, 0, sizeof(p));
  cnt = 1;
  sum = 0;
  for (int i = 1; i <= n; i++)
    if (e[i].l <= mid && e[i].c != 1) {
      if (e[i].c & 1)
        Anode(0, i, e[i].p);
      else
        Anode(i, T, e[i].p);
      sum += e[i].p;
      for (int j = i + 1; j <= n; j++)
        if (e[j].l <= mid && e[j].c != 1) {
          if (Not_Prime[e[i].c + e[j].c]) continue;
          if (e[i].c & 1)
            Anode(i, j, 0x7fffffff);
          else
            Anode(j, i, 0x7fffffff);
        }
    }
}
void Build2(int mid) {
  memset(p, 0, sizeof(p));
  cnt = 1;
  sum = 0;
  for (int i = 1; i <= n; i++)
    if (e[i].l <= mid && Not_Prime[e[i].c + 1]) {
      if (e[i].c & 1)
        Anode(0, i, e[i].p);
      else
        Anode(i, T, e[i].p);
      sum += e[i].p;
      for (int j = i + 1; j <= n; j++)
        if (e[j].l <= mid && Not_Prime[e[j].c + 1]) {
          if (Not_Prime[e[i].c + e[j].c]) continue;
          if (e[i].c & 1)
            Anode(i, j, 0x7fffffff);
          else
            Anode(j, i, 0x7fffffff);
        }
    }
}
bool Bfs() {
  queue<int> q;
  q.push(0);
  for (int i = 0; i <= T; i++) Level[i] = 0;
  Level[S] = 1;
  while (!q.empty()) {
    int k = q.front();
    q.pop();
    for (int i = p[k]; i; i = nextedge[i]) {
      int v = b[i], f = w[i];
      if (!Level[v] && f) {
        Level[v] = Level[k] + 1;
        q.push(v);
      }
    }
  }
  return Level[T];
}
int Dfs(int x, int maxf) {
  if (x == T || !maxf) return maxf;
  int rtn = 0;
  for (int i = cur[x]; i && maxf > rtn; i = nextedge[i]) {
    int v = b[i], f = w[i];
    if (Level[v] == Level[x] + 1 && f) {
      f = Dfs(v, min(maxf - rtn, f));
      w[i] -= f;
      w[i ^ 1] += f;
      rtn += f;
      if (w[i]) cur[x] = i;
    }
  }
  return rtn;
}
int Dinic() {
  int rtn = 0;
  while (Bfs()) {
    for (int i = 0; i <= T; i++) cur[i] = p[i];
    rtn += Dfs(0, 0x7fffffff);
  }
  return rtn;
}
bool Judge(int mid) {
  Build1(mid);
  int tmp1 = sum - Dinic();
  Build2(mid);
  int tmp2 = sum - Dinic();
  int mx = 0;
  for (int i = 1; i <= n; i++)
    if (e[i].l <= mid && e[i].c == 1) mx = max(mx, e[i].p);
  return max(tmp1, tmp2 + mx) >= m;
}
void Binary_Search() {
  while (l <= r) {
    int mid = l + r >> 1;
    if (Judge(mid))
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%d\n", ans);
}
int main() {
  n = read(), m = read();
  T = n + 1;
  for (int i = 1; i <= n; i++)
    e[i].p = read(), e[i].c = read(), e[i].l = read(), l = min(l, e[i].l),
    r = max(r, e[i].l);
  Get_Prime();
  Binary_Search();
  return 0;
}
