#include <bits/stdc++.h>
template <class T>
T Max(const T &a, const T &b) {
  return a > b ? a : b;
}
template <class T>
T Min(const T &a, const T &b) {
  return a < b ? a : b;
}
const int SN = 1000 + 10;
const int SM = SN * SN + 10;
const int inf = 0x3fffffff;
int n, m, k, p[SN], c[SN], l[SN], max1, maxk, max2, s, t, tot, ans;
int prime[2 * SM], cnt;
bool v[2 * SM];
void pre_work() {
  v[1] = 1;
  for (int i = 2; i <= 200000; i++) {
    if (!v[i]) prime[++cnt] = i;
    for (int j = 1; j <= cnt && prime[j] * i <= 200000; j++) {
      v[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
void Read(int &x) {
  int in = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    in = in * 10 + ch - '0';
    ch = getchar();
  }
  x = in * f;
}
namespace flow {
int que[SN], cur[SN], d[SN], head[SN], cap[SM << 1], vis[SN], num = 1;
struct Edge {
  int v, next;
} E[SM << 1];
void Add(int u, int v, int w) {
  E[++num].v = v, E[num].next = head[u], head[u] = num, cap[num] = w;
  E[++num].v = u, E[num].next = head[v], head[v] = num, cap[num] = 0;
}
int Bfs() {
  memset(d, 0, sizeof d);
  int front = 1, tail = 1;
  que[front] = s, d[s] = 1;
  int now, to;
  while (front <= tail) {
    now = que[front++];
    for (int i = head[now]; i; i = E[i].next) {
      to = E[i].v;
      if (!d[to] && cap[i]) d[to] = d[now] + 1, que[++tail] = to;
      if (d[t]) return 1;
    }
  }
  return d[t];
}
int Dfs(int u, int v) {
  if (u == t || !v) return v;
  int f = 0;
  for (int &i = cur[u]; i; i = E[i].next) {
    int to = E[i].v;
    if (d[to] == d[u] + 1 && cap[i])
      if (f = Dfs(to, Min(v, cap[i]))) return cap[i] -= f, cap[i ^ 1] += f, f;
  }
  return 0;
}
int dinic() {
  int xx, ans = 0;
  while (Bfs()) {
    memcpy(cur, head, sizeof head);
    while (xx = Dfs(s, inf)) ans += xx;
  }
  return ans;
}
}  // namespace flow
using namespace flow;
int fuck(int mid) {
  memset(head, 0, sizeof head);
  memset(vis, 0, sizeof vis);
  num = 1, max1 = 0, max2 = 0, tot = 0;
  for (int i = 1; i <= n; i++) {
    if (l[i] > mid) continue;
    if (c[i] == 1) {
      if (max1 < p[i]) {
        tot -= max1, max1 = p[i], tot += max1;
        vis[max2] = 0, max2 = i, vis[i] = 1;
      }
    } else {
      vis[i] = 1, tot += p[i];
      if (c[i] & 1)
        Add(s, i, p[i]);
      else
        Add(i, t, p[i]);
    }
  }
  if (max1) Add(s, max2, max1);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (!(i ^ j)) continue;
      if (c[i] & 1 && !(c[j] & 1) && vis[i] && vis[j] && !v[c[i] + c[j]])
        Add(i, j, inf);
    }
  return tot - dinic();
}
int main() {
  Read(n), Read(k);
  t = n + 1;
  pre_work();
  for (int i = 1; i <= n; i++) {
    Read(p[i]), Read(c[i]), Read(l[i]);
    maxk = Max(maxk, l[i]);
  }
  int l = 1, r = maxk;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (fuck(mid) >= k)
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  if (ans)
    printf("%d\n", ans);
  else
    puts("-1");
  return 0;
}
