#include <bits/stdc++.h>
using namespace std;
const int iinf = 1 << 29;
const long long inf = 1ll << 60;
const long long mod = 1e9 + 7;
void GG() {
  cout << "-1\n";
  exit(0);
}
long long mpow(long long a, long long n, long long mo = mod) {
  long long re = 1;
  while (n > 0) {
    if (n & 1) re = re * a % mo;
    a = a * a % mo;
    n >>= 1;
  }
  return re;
}
long long inv(long long b, long long mo = mod) {
  if (b == 1) return b;
  return (mo - mo / b) * inv(mo % b) % mo;
}
const int maxn = 2e5 + 5;
struct Dinic {
  struct Edge {
    int to, rev;
    long long cap, flow = 0;
    Edge(int to, int rev, long long cap) : to(to), rev(rev), cap(cap) {}
  };
  vector<vector<Edge> > g;
  int n;
  int second, t;
  vector<int> level, ptr;
  Dinic(int n, int second, int t) : n(n), second(second), t(t) {
    level.resize(n, -1);
    ptr.resize(n);
    g.resize(n);
  }
  void add(int v, int u, long long cap) {
    g[v].push_back({u, (int)g[u].size(), cap});
    g[u].push_back({v, (int)g[v].size() - 1, 0});
  }
  bool bfs() {
    queue<int> q({second});
    level[second] = 0;
    while (!q.empty() && level[t] == -1) {
      int v = q.front();
      q.pop();
      for (auto &e : g[v]) {
        if (e.cap - e.flow == 0) continue;
        int u = e.to;
        if (level[u] == -1) {
          level[u] = level[v] + 1;
          q.push(u);
        }
      }
    }
    return level[t] != -1;
  }
  long long dfs(int v, long long amt) {
    if (amt == 0 || v == t) return amt;
    for (; ptr[v] < (int)g[v].size(); ptr[v]++) {
      Edge &e = g[v][ptr[v]];
      int u = e.to;
      if (level[u] == level[v] + 1) {
        long long tt = dfs(u, min(amt, e.cap - e.flow));
        if (tt == 0) continue;
        e.flow += tt;
        g[e.to][e.rev].flow -= tt;
        return tt;
      }
    }
    return 0;
  }
  long long mf() {
    long long re = 0;
    while (bfs()) {
      while (long long amt = dfs(second, inf)) re += amt;
      fill(level.begin(), level.end(), -1);
      fill(ptr.begin(), ptr.end(), 0);
    }
    return re;
  }
};
bool np[maxn];
void build() {
  for (int i = (2); i < (maxn); i++) {
    if (!np[i])
      for (int j = i + i; j < maxn; j += i) {
        np[j] = 1;
      }
  }
}
vector<pair<pair<int, int>, int> > v;
long long mx(int moe) {
  vector<pair<int, int> > go;
  long long S = 0;
  map<int, int> mp;
  for (auto &x : v) {
    if (x.second <= moe) {
      if (x.first.second != 1)
        mp[x.first.second] += x.first.first;
      else
        mp[x.first.second] =
            max(mp[x.first.second],
                (__typeof__(mp[x.first.second]))(x.first.first));
    }
  }
  vector<int> have;
  map<int, int> id;
  int idat = 0;
  for (pair<int, int> x : mp) {
    id[x.first] = idat++;
    go.push_back(x);
    S += x.second;
  }
  int n = (int)go.size() + 5;
  int second = n - 1, t = n - 2;
  Dinic dd(n, second, t);
  for (int i = 0; i < ((int)go.size()); i++) {
    if (go[i].first & 1) {
      dd.add(id[go[i].first], t, go[i].second);
    } else {
      dd.add(second, id[go[i].first], go[i].second);
    }
  }
  for (int i = 0; i < ((int)go.size()); i++)
    for (int j = 0; j < ((int)go.size()); j++) {
      int a = go[i].first, b = go[j].first;
      if (a % 2 == 0 && b % 2 == 1) {
        if (np[a + b] == 0) {
          dd.add(id[a], id[b], inf);
        }
      }
    }
  return S - dd.mf();
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  build();
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < (n); i++) {
    int a, b, c;
    cin >> a >> b >> c;
    v.push_back({{a, b}, c});
  }
  int l = 0, r = n + 2;
  while (l != r) {
    int mid = (l + r) / 2;
    if (mx(mid) >= k) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  if (l > n) {
    GG();
  }
  cout << l << endl;
}
