#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using int64 = long long int;
template <typename T>
void chmax(T &a, T b) {
  a = max(a, b);
}
template <typename T>
void chmin(T &a, T b) {
  a = min(a, b);
}
template <typename T>
void chadd(T &a, T b) {
  a = a + b;
}
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
template <typename CapTp = int, typename CostTp = int>
struct Edge {
  int to, rev;
  CapTp cap;
  CostTp cost;
  bool is_rev;
  Edge(int t, bool f, int r, CapTp ca, CostTp co = 0)
      : to(t), rev(r), cap(ca), cost(co), is_rev(f) {}
};
template <typename CapTp = int>
struct Dinic {
  using Graph = vector<vector<Edge<CapTp> > >;
  Graph G;
  vector<int> level, iter;
  const CapTp IA;
  vector<pair<int, int> > r_edges;
  Dinic(int N, CapTp IA_ = 1 << 29) : IA(IA_) {
    G.resize(N);
    level.resize(N);
    iter.resize(N);
  }
  void add_edge(int from, int to, CapTp cap) {
    G[from].emplace_back(to, false, G[to].size(), cap);
    G[to].emplace_back(from, true, G[from].size() - 1, 0);
    r_edges.emplace_back(to, G[to].size() - 1);
  }
  CapTp get_flowed_cap(size_t k) {
    if (r_edges.size() <= k) return -1;
    int v, i;
    tie(v, i) = r_edges[k];
    return G[v][i].cap;
  }
  void bfs(int s) {
    fill(level.begin(), level.end(), -1);
    queue<int> que;
    que.push(s);
    level[s] = 0;
    while (!que.empty()) {
      int temp = que.front();
      que.pop();
      for (size_t i = 0; i < G[temp].size(); i++) {
        auto &e = G[temp][i];
        if (e.cap > 0 && level[e.to] < 0) {
          level[e.to] = level[temp] + 1;
          que.push(e.to);
        }
      }
    }
  }
  CapTp dfs(int v, int t, CapTp f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < (int)G[v].size(); i++) {
      auto &e = G[v][i];
      if (e.cap > 0 && level[v] < level[e.to]) {
        CapTp d = dfs(e.to, t, min(f, e.cap));
        if (d > 0) {
          e.cap -= d;
          G[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
  CapTp max_flow(int s, int t) {
    CapTp flow = 0.0, f;
    while (1) {
      bfs(s);
      if (level[t] < 0) return flow;
      fill(iter.begin(), iter.end(), 0);
      while ((f = dfs(s, t, IA)) > 0) flow += f;
    }
  }
};
template <typename flow_type>
struct Dinic_lr {
  Dinic<flow_type> fl;
  int S, T;
  flow_type sum_lb;
  Dinic_lr() {}
  Dinic_lr(int N) : fl(N + 2, 0), S(N), T(N + 1), sum_lb(0) {}
  void add_edge(int u, int v, flow_type lb, flow_type ub) {
    assert(0 <= lb && lb <= ub);
    if (u == v || ub == 0) return;
    fl.add_edge(u, v, ub - lb);
    fl.add_edge(S, v, lb);
    fl.add_edge(u, T, lb);
    sum_lb += lb;
  }
  flow_type max_flow(int s, int t) {
    flow_type a = fl.max_flow(S, T);
    flow_type b = fl.max_flow(s, T);
    flow_type c = fl.max_flow(S, t);
    flow_type d = fl.max_flow(s, t);
    return (a + c == sum_lb && a + b == sum_lb) ? b + d : -1;
  }
};
const tuple<int, int, int> NIL(-1, -1, -1);
bool solve(int K, const vector<tuple<int, int, int> > &items,
           const vector<bool> &is_prime) {
  int N = items.size();
  vector<int> parity(N);
  int source = N, sink = source + 1;
  Dinic<ll> fl(N + 2);
  int sum = 0;
  for (int i = 0; i < N; i++) {
    parity[i] = get<1>(items[i]) % 2;
    int v = get<0>(items[i]);
    sum += 2 * v;
    if (parity[i] == 0) {
      fl.add_edge(source, i, 2 * v);
      fl.add_edge(i, sink, v);
    } else {
      fl.add_edge(source, i, v);
      fl.add_edge(i, sink, 2 * v);
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (parity[i] != 0 or parity[j] != 1) continue;
      int v = get<1>(items[i]) + get<1>(items[j]);
      if (is_prime[v]) {
        fl.add_edge(i, j, INF);
      }
    }
  }
  int f = fl.max_flow(source, sink);
  return f <= sum - K and sum - K >= 0;
}
int main() {
  int N, K;
  scanf("%d%d", &N, &K);
  vector<tuple<int, int, int> > item1, item2;
  vector<int> level;
  for (int i = 0; i < N; i++) {
    int p, c, l;
    scanf("%d%d%d", &p, &c, &l);
    if (c == 1)
      item1.emplace_back(p, c, l);
    else
      item2.emplace_back(p, c, l);
    level.emplace_back(l);
  }
  sort(level.begin(), level.end());
  level.erase(unique(level.begin(), level.end()), level.end());
  const int P = 200010;
  vector<bool> is_prime(P + 10, true);
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= P; i++) {
    if (!is_prime[i]) continue;
    for (int k = 2 * i; k <= P; k += i) is_prime[k] = false;
  }
  int ans = INF;
  for (auto l : level) {
    vector<tuple<int, int, int> > items;
    for (auto e : item2)
      if (get<2>(e) <= l) items.emplace_back(e);
    tuple<int, int, int> one(NIL);
    for (auto e : item1) {
      if (get<2>(e) > l) continue;
      if (get<0>(e) > get<0>(one)) one = e;
    }
    if (one != NIL) items.emplace_back(one);
    if (solve(K, items, is_prime)) ans = l;
    if (ans != INF) break;
  }
  printf("%d\n", (ans == INF ? -1 : ans));
  return 0;
}
