#include <bits/stdc++.h>
using namespace std;
inline long long rd() {
  long long x = 0;
  int ch = getchar(), f = 1;
  while (!isdigit(ch) && (ch != '-') && (ch != EOF)) ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void rt(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10)
    rt(x / 10), putchar(x % 10 + '0');
  else
    putchar(x + '0');
}
const int maxn = 105, maxp = 200005, maxm = 100000;
void GetAnswer(int ans) {
  rt(ans), putchar('\n');
  exit(0);
}
void NoAnswer() {
  puts("-1");
  exit(0);
}
struct obj {
  int p, c, l;
  bool operator<(const obj& x) const { return l < x.l; }
} a[maxn];
int mn[maxp], prm[50000], isp[maxp], pc;
void sieve(int n) {
  for (int i = 2; i <= (int)(n); i++) {
    if (!mn[i]) isp[i] = 1, prm[mn[i] = ++pc] = i;
    for (int j = 1; j <= (int)(mn[i]); j++) {
      int k = i * prm[j];
      if (k > n) break;
      mn[k] = j;
    }
  }
}
int S, T, ONE, h, t, q[maxn];
int dep[maxn], hd[maxn], to[maxm], nx[maxm], cap[maxm], cnt;
void addedge(int u, int v, int w) {
  to[cnt] = v;
  nx[cnt] = hd[u];
  cap[cnt] = w;
  hd[u] = cnt++;
  to[cnt] = u;
  nx[cnt] = hd[v];
  cap[cnt] = 0;
  hd[v] = cnt++;
}
bool bfs() {
  h = 1, t = 0;
  q[++t] = S;
  memset(dep, -1, sizeof dep);
  dep[S] = 0;
  while (h <= t) {
    int u = q[h++];
    for (int i = hd[u]; ~i; i = nx[i]) {
      int v = to[i];
      if (cap[i] && dep[v] == -1) {
        dep[v] = dep[u] + 1;
        if (v == T) return 1;
        q[++t] = v;
      }
    }
  }
  return 0;
}
int dfs(int u, int flow) {
  if (u == T || !flow) return flow;
  int ret = 0, f;
  for (int i = hd[u]; ~i; i = nx[i]) {
    int v = to[i];
    if (dep[v] == dep[u] + 1 && (f = dfs(v, min(flow, cap[i])))) {
      ret += f, flow -= f;
      cap[i] -= f, cap[i ^ 1] += f;
      if (!flow) break;
    }
  }
  if (!ret) dep[u] = -1;
  return ret;
}
int Dinic() {
  int ret = 0;
  while (bfs()) ret += dfs(S, (1 << 29));
  return ret;
}
int solve(int n) {
  S = 0, ONE = n + 1, T = n + 2;
  memset(hd, -1, sizeof hd);
  cnt = 0;
  int mxv = 0, ans = 0;
  for (int i = 1; i <= (int)(n); i++) {
    if (a[i].c == 1)
      mxv = max(mxv, a[i].p);
    else {
      ans += a[i].p;
      if (a[i].c & 1) {
        addedge(S, i, a[i].p);
        for (int j = 1; j <= (int)(n); j++)
          if (isp[a[i].c + a[j].c]) addedge(i, j, (1 << 29));
      } else {
        addedge(i, T, a[i].p);
      }
    }
  }
  ans += mxv;
  if (mxv) {
    addedge(S, ONE, mxv);
    for (int i = 1; i <= (int)(n); i++)
      if (a[i].c != 1 && isp[a[i].c + 1]) addedge(ONE, i, (1 << 29));
  }
  return ans - Dinic();
}
int n, k;
int main() {
  sieve(200000);
  n = rd(), k = rd();
  for (int i = 1; i <= (int)(n); i++)
    a[i].p = rd(), a[i].c = rd(), a[i].l = rd();
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= (int)(n); i++) {
    while (i < n && a[i].l == a[i + 1].l) i++;
    if (solve(i) >= k) GetAnswer(a[i].l);
  }
  NoAnswer();
}
