#include <bits/stdc++.h>
using namespace std;
const long long MAX = 105;
const long long MAXV = 2e5 + 1;
const long long INF = 1e9;
bool prime[MAXV];
void sieve() {
  memset(prime, true, sizeof(prime));
  prime[0] = prime[1] = false;
  for (long long i = 2; i * i < MAXV; i++) {
    if (prime[i]) {
      for (long long j = i * i; j < MAXV; j += i) prime[j] = false;
    }
  }
}
long long n, k, p[MAX], c[MAX], l[MAX];
struct edge {
  int from, to, flow, index;
  long long cap;
  edge(int from, int to, long long cap, int flow, int index)
      : from(from), to(to), cap(cap), flow(flow), index(index) {}
};
struct PushRelabel {
  int n;
  vector<vector<edge>> g;
  vector<long long> excess;
  vector<int> height, active, count;
  queue<int> Q;
  PushRelabel(int n)
      : n(n), g(n), excess(n), height(n), active(n), count(2 * n) {}
  void addEdge(int from, int 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(int v) {
    if (!active[v] && excess[v] > 0) {
      active[v] = true;
      Q.push(v);
    }
  }
  void push(edge &e) {
    int amt = (int)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(int v) {
    count[height[v]]--;
    int 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(int k) {
    for (int 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(int v) {
    for (int 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(int source, int 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()) {
      int 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;
  }
};
bool f(long long lvl) {
  vector<long long> v = {0};
  long long sm = 0, mx = -1, id = 0;
  for (long long i = 1; i <= n; i++) {
    if (l[i] <= lvl) {
      if (c[i] != 1) {
        sm += p[i];
        v.push_back(i);
      } else {
        if (p[i] > mx) {
          mx = p[i];
          id = i;
        }
      }
    }
  }
  if (mx != -1) {
    v.push_back(id);
    sm += p[id];
  }
  long long cnt = v.size() - 1;
  PushRelabel Network(cnt + 2);
  long long s = 0, t = cnt + 1;
  vector<int> odd, even;
  odd.push_back(0), even.push_back(0);
  for (int i = 1; i <= cnt; i++) {
    if (c[v[i]] & 1)
      odd.push_back(v[i]);
    else
      even.push_back(v[i]);
  }
  int os = odd.size() - 1, es = even.size() - 1;
  for (int i = 1; i <= os; i++) Network.addEdge(s, i, p[odd[i]]);
  for (int i = 1; i <= es; i++) Network.addEdge(os + i, t, p[even[i]]);
  for (int i = 1; i <= os; i++) {
    for (int j = 1; j <= es; j++) {
      int idx1 = odd[i], idx2 = even[j];
      if (prime[c[idx1] + c[idx2]]) Network.addEdge(i, os + j, INF);
    }
  }
  long long flow = Network.max_flow(s, t);
  long long mxpow = sm - flow;
  return mxpow >= k;
}
void solve() {
  long long l = 0, r = n + 1;
  while (r - l > 1) {
    long long mid = (l + r) / 2;
    if (f(mid))
      r = mid;
    else
      l = mid;
  }
  if (f(r))
    cout << r;
  else
    cout << -1;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  sieve();
  cin >> n >> k;
  for (long long i = 1; i <= n; i++) cin >> p[i] >> c[i] >> l[i];
  solve();
  return 0;
}
