#include <bits/stdc++.h>
using namespace std;
namespace Dinic {
typedef int T;
struct edge {
  int from, to;
  T f;
};
const int MAX = 2e4 + 5;
const T INF = 1e9;
int n, s, t, pt[MAX], d[MAX];
vector<edge> e;
vector<int> g[MAX];
queue<int> q;
void init(int n_, int s_, int t_) {
  n = n_, s = s_, t = t_;
  for (int i = 1; i <= n; i++) g[i].clear();
  e.clear();
}
void addEdge(int from, int to, T c) {
  edge ed;
  ed.from = from, ed.to = to, ed.f = c;
  e.push_back(ed);
  g[from].push_back((int)e.size() - 1);
  ed.from = to, ed.to = from, ed.f = 0;
  e.push_back(ed);
  g[to].push_back((int)e.size() - 1);
}
bool bfs() {
  for (int i = 1; i <= n; i++) d[i] = -1;
  d[s] = 0;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int id : g[u]) {
      int v = e[id].to;
      if (d[v] == -1 && e[id].f > 0) {
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }
  return d[t] != -1;
}
T dfs(int u, T flow = INF) {
  if (u == t) return flow;
  for (; pt[u] < (int)g[u].size(); pt[u]++) {
    int id = g[u][pt[u]];
    int v = e[id].to;
    if (d[u] + 1 != d[v] || e[id].f == 0) continue;
    T pushed = dfs(v, min(flow, e[id].f));
    if (pushed > 0) {
      e[id].f -= pushed;
      e[id ^ 1].f += pushed;
      return pushed;
    }
  }
  return 0;
}
T getMaxFlow() {
  T ans = 0;
  while (1) {
    if (!bfs()) break;
    for (int i = 1; i <= n; i++) pt[i] = 0;
    T f;
    while ((f = dfs(s))) ans += f;
  }
  return ans;
}
}  // namespace Dinic
const int M = 2e5 + 5;
int n, k, lft[105], rgt[105], p[105], c[105], l[105], comp[M], mk[105];
inline int isPrime(int x) { return !comp[x]; }
int can(int x) {
  int cnt = 0;
  int mx_one = 0;
  int id = 0;
  int tot = 0;
  int s = ++id;
  int t = ++id;
  for (int i = 1; i <= n; i++) {
    if (l[i] > x) continue;
    if (c[i] == 1) {
      cnt++;
      mx_one = max(mx_one, p[i]);
      continue;
    }
    tot += p[i];
    if (c[i] % 2 == 1)
      lft[i] = ++id;
    else
      rgt[i] = ++id;
  }
  Dinic::init(id, s, t);
  for (int i = 1; i <= n; i++) {
    if (l[i] > x || c[i] == 1) continue;
    if (c[i] % 2 == 1)
      Dinic::addEdge(s, lft[i], p[i]);
    else
      Dinic::addEdge(rgt[i], t, p[i]);
  }
  for (int i = 1; i <= n; i++) {
    if (l[i] > x || c[i] == 1 || c[i] % 2 == 0) continue;
    for (int j = 1; j <= n; j++) {
      if (l[j] > x || c[j] % 2 == 1) continue;
      if (isPrime(c[i] + c[j])) Dinic::addEdge(lft[i], rgt[j], Dinic::INF);
    }
  }
  int ans = tot - Dinic::getMaxFlow();
  if (mx_one > 0) {
    Dinic::init(id, s, t);
    tot = 0;
    for (int i = 1; i <= n; i++) {
      mk[i] = 0;
      if (l[i] <= x) tot += p[i];
    }
    for (int i = 1; i <= n; i++) {
      if (l[i] > x) continue;
      if (isPrime(1 + c[i])) {
        mk[i] = 1;
        tot -= p[i];
      }
    }
    for (int i = 1; i <= n; i++) {
      if (l[i] > x || c[i] == 1 || mk[i]) continue;
      if (c[i] % 2 == 1)
        Dinic::addEdge(s, lft[i], p[i]);
      else
        Dinic::addEdge(rgt[i], t, p[i]);
    }
    for (int i = 1; i <= n; i++) {
      if (l[i] > x || mk[i] || c[i] == 1 || c[i] % 2 == 0) continue;
      for (int j = 1; j <= n; j++) {
        if (l[j] > x || mk[j] || c[j] % 2 == 1) continue;
        if (isPrime(c[i] + c[j])) {
          Dinic::addEdge(lft[i], rgt[j], Dinic::INF);
        }
      }
    }
    ans = max(ans, tot + mx_one - Dinic::getMaxFlow());
  }
  return ans >= k;
}
int main() {
  comp[0] = comp[1] = 1;
  for (int i = 2; i < M; i++) {
    if (comp[i]) continue;
    for (int j = 2 * i; j < M; j += i) comp[j] = 1;
  }
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d%d%d", &p[i], &c[i], &l[i]);
  int st = 1, nd = n, ans = INT_MAX;
  while (st <= nd) {
    int mid = (st + nd) >> 1;
    if (can(mid)) {
      ans = min(ans, mid);
      nd = mid - 1;
    } else
      st = mid + 1;
  }
  if (ans == INT_MAX) ans = -1;
  printf("%d\n", ans);
  return 0;
}
