#include <bits/stdc++.h>
using namespace std;
const int N = 106, M = 2e5 + 87, inf = 1e7;
struct Dinic {
  int n, s, t;
  struct edge {
    int fr, to, rd;
    edge() {}
    edge(int a, int b, int c) : fr(a), to(b), rd(c) {}
  };
  vector<edge> E;
  vector<int> g[N];
  int lv[N], idx[N];
  void init(int _n, int _s, int _t) {
    n = _n;
    s = _s;
    t = _t;
    E.clear();
    for (int i(0), _B(n); i < _B; ++i) g[i].clear();
  }
  void addE(int u, int v, int c) {
    E.emplace_back(u, v, c);
    E.emplace_back(v, u, 0);
    g[u].push_back(((int)(E.size())) - 2);
    g[v].push_back(((int)(E.size())) - 1);
  }
  bool bfs() {
    fill_n(lv, n, 0);
    fill_n(idx, n, 0);
    lv[s] = 1;
    queue<int> q;
    q.push(s);
    while (((int)(q.size()))) {
      int u = q.front();
      q.pop();
      if (lv[u] == lv[t]) break;
      for (int i : g[u])
        if (E[i].rd) {
          int v = E[i].to;
          if (!lv[v]) {
            lv[v] = lv[u] + 1;
            q.push(v);
          }
        }
    }
    return lv[t];
  }
  int dfs(int u, int a) {
    if (u == t) return a;
    if (lv[u] >= lv[t] || !a) return 0;
    int ans = 0;
    for (int& i = idx[u]; i < ((int)(g[u].size())); ++i) {
      int x = g[u][i];
      int v = E[x].to;
      if (lv[v] == lv[u] + 1) {
        int c = dfs(v, min(a, E[x].rd));
        a -= c;
        E[x].rd -= c;
        E[x ^ 1].rd += c;
        ans += c;
        if (!a) break;
      }
    }
    return ans;
  }
  int mf() {
    int ans = 0;
    while (bfs()) ans += dfs(s, inf);
    return ans;
  }
} flower;
bool sev[M];
vector<tuple<int, int, int> > a, a1;
int vl[N], co[N];
vector<int> g[N];
void pre() {
  vector<int> p;
  sev[0] = sev[1] = 1;
  for (int i(2), _B(M); i < _B; ++i) {
    if (!sev[i]) p.push_back(i);
    for (auto j : p) {
      if (i * j >= M) break;
      sev[i * j] = 1;
      if (i % j == 0) break;
    }
  }
}
void dfs(int u, int c) {
  if (co[u] != -1) return;
  co[u] = c;
  for (int v : g[u]) dfs(v, c ^ 1);
}
int solve(int ml) {
  int m;
  for (m = 0; m < ((int)(a.size())) && get<0>(a[m]) <= ml; ++m)
    ;
  for (int i = 0; i < ((int)(a1.size())) && get<0>(a1[i]) <= ml; ++i)
    get<2>(a[0]) = max(get<2>(a[0]), get<2>(a1[i]));
  int s = m, t = m + 1;
  flower.init(m + 2, s, t);
  int ans = 0;
  for (int i(0), _B(m); i < _B; ++i) {
    ans += get<2>(a[i]);
    if (co[i] == 0) {
      flower.addE(s, i, get<2>(a[i]));
      for (auto j : g[i]) {
        if (j >= m) break;
        flower.addE(i, j, inf);
      }
    } else {
      flower.addE(i, t, get<2>(a[i]));
    }
  }
  ans -= flower.mf();
  get<2>(a[0]) = 0;
  return ans;
}
int main() {
  pre();
  int n, k;
  scanf("%d%d", &n, &k);
  a.emplace_back(0, 1, 0);
  for (int i(0), _B(n); i < _B; ++i) {
    int p, c, l;
    scanf("%d%d%d", &p, &c, &l);
    if (c == 1)
      a1.emplace_back(l, c, p);
    else
      a.emplace_back(l, c, p);
    vl[i] = l;
  }
  sort(a.begin(), a.end());
  sort(a1.begin(), a1.end());
  sort(vl, vl + n);
  int m = unique(vl, vl + n) - vl;
  for (int i(1), _B(((int)(a.size()))); i < _B; ++i)
    for (int j = 0; j < i; ++j)
      if (!sev[get<1>(a[j]) + get<1>(a[i])]) {
        g[i].push_back(j);
        g[j].push_back(i);
      }
  fill_n(co, ((int)(a.size())), -1);
  for (int i(0), _B(((int)(a.size()))); i < _B; ++i) dfs(i, 0);
  int lo = 0, hi = m - 1;
  while (lo <= hi) {
    int mi = (lo + hi) / 2;
    if (solve(vl[mi]) < k)
      lo = mi + 1;
    else
      hi = mi - 1;
  }
  printf("%d\n", lo == m ? -1 : vl[lo]);
}
