#include <bits/stdc++.h>
using namespace std;
const long long N = 105;
const long long M = 2e5 + 5;
struct edge {
  long long from, to, cap, flow, index;
  edge(long long from, long long to, long long cap, long long flow,
       long long index)
      : from(from), to(to), cap(cap), flow(flow), index(index) {}
};
struct PushRelabel {
  long long n;
  vector<vector<edge> > g;
  vector<long long> excess;
  vector<long long> height, active, count;
  queue<long long> Q;
  PushRelabel(long long n)
      : n(n), g(n), excess(n), height(n), active(n), count(2 * n) {}
  void addEdge(long long from, long long to, long long cap) {
    g[from].push_back(edge(from, to, cap, 0, g[to].size()));
    if (from == to) g[from].back().index++;
    g[to].push_back(edge(to, from, 0, 0, g[from].size() - 1));
  }
  void enqueue(long long v) {
    if (!active[v] && excess[v] > 0) {
      active[v] = true;
      Q.push(v);
    }
  }
  void push(edge &e) {
    long long amt = (long long)min(excess[e.from], (long long)e.cap - e.flow);
    if (height[e.from] <= height[e.to] || amt == 0) return;
    e.flow += amt;
    g[e.to][e.index].flow -= amt;
    excess[e.to] += amt;
    excess[e.from] -= amt;
    enqueue(e.to);
  }
  void relabel(long long v) {
    count[height[v]]--;
    long long d = 2 * n;
    for (auto &it : g[v]) {
      if (it.cap - it.flow > 0) d = min(d, height[it.to] + 1);
    }
    height[v] = d;
    count[height[v]]++;
    enqueue(v);
  }
  void gap(long long k) {
    for (long long v = 0; v < n; v++) {
      if (height[v] < k) continue;
      count[height[v]]--;
      height[v] = max(height[v], n + 1);
      count[height[v]]++;
      enqueue(v);
    }
  }
  void discharge(long long v) {
    for (long long i = 0; excess[v] > 0 && i < g[v].size(); i++) push(g[v][i]);
    if (excess[v] > 0) {
      if (count[height[v]] == 1)
        gap(height[v]);
      else
        relabel(v);
    }
  }
  long long max_flow(long long source, long long dest) {
    count[0] = n - 1;
    count[n] = 1;
    height[source] = n;
    active[source] = active[dest] = 1;
    for (auto &it : g[source]) {
      excess[source] += it.cap;
      push(it);
    }
    while (!Q.empty()) {
      long long v = Q.front();
      Q.pop();
      active[v] = false;
      discharge(v);
    }
    long long max_flow = 0;
    for (auto &e : g[source]) max_flow += e.flow;
    return max_flow;
  }
};
long long n, k;
long long p[N], c[N], l[N], sieve[M];
void precompute() {
  fill(sieve + 2, sieve + M, 1);
  for (long long i = 2; i < N; i++) {
    if (!sieve[i]) continue;
    for (long long j = 2; i * j < N; j++) sieve[i * j] = 0;
  }
}
long long check(long long x) {
  long long sum = 0, sumones = 0, bestone = 0;
  vector<pair<long long, long long> > odds, evens;
  for (long long i = 1; i <= n; i++) {
    if (l[i] <= x) {
      sum += p[i];
      if (c[i] == 1) {
        sumones += p[i];
        bestone = max(bestone, p[i]);
      } else if (c[i] % 2)
        odds.push_back({p[i], c[i]});
      else
        evens.push_back({p[i], c[i]});
    }
  }
  if (bestone) {
    sum = sum - sumones + bestone;
    odds.push_back({bestone, 1});
  }
  PushRelabel flow(odds.size() + evens.size() + 2);
  long long asz = odds.size(), bsz = evens.size();
  for (long long i = 0; i < asz; i++) {
    flow.addEdge(0, i + 1, odds[i].first);
    for (long long j = 0; j < bsz; j++) {
      if (i == 0) flow.addEdge(j + asz + 1, asz + bsz + 1, evens[j].first);
      if (sieve[odds[i].second + evens[j].second])
        flow.addEdge(i + 1, j + asz + 1, 1e9);
    }
  }
  long long ans = sum - flow.max_flow(0, asz + bsz + 1);
  return ans >= k;
}
long long binsearch(long long lo, long long hi) {
  while (lo < hi) {
    long long mid = (lo + hi) / 2;
    if (check(mid))
      hi = mid;
    else
      lo = mid + 1;
  }
  return lo;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  precompute();
  cin >> n >> k;
  for (long long i = 1; i <= n; i++) cin >> p[i] >> c[i] >> l[i];
  long long ans = binsearch(1, 100);
  if (!check(ans)) ans = -1;
  cout << ans << "\n";
  return 0;
}
