#include <bits/stdc++.h>
using namespace std;
template <typename T>
void unique(T &c) {
  c.erase(std::unique(c.begin(), c.end()), c.end());
}
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) {
    os << vec[i];
    if (i + 1 != vec.size()) os << " ";
  }
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &st) {
  for (auto itr = st.begin(); itr != st.end(); ++itr) {
    os << *itr;
    auto titr = itr;
    if (++titr != st.end()) os << " ";
  }
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &st) {
  for (auto itr = st.begin(); itr != st.end(); ++itr) {
    os << *itr;
    auto titr = itr;
    if (++titr != st.end()) os << " ";
  }
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &st) {
  for (auto itr = st.begin(); itr != st.end(); ++itr) {
    os << *itr;
    auto titr = itr;
    if (++titr != st.end()) os << " ";
  }
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &st) {
  for (auto itr = st.begin(); itr != st.end(); ++itr) {
    os << *itr;
    auto titr = itr;
    if (++titr != st.end()) os << " ";
  }
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
  for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
    os << "(" << itr->first << ", " << itr->second << ")";
    auto titr = itr;
    if (++titr != mp.end()) os << " ";
  }
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const unordered_map<T1, T2> &mp) {
  for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
    os << "(" << itr->first << ", " << itr->second << ")";
    auto titr = itr;
    if (++titr != mp.end()) os << " ";
  }
  return os;
}
using ll = long long int;
using P = pair<int, int>;
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1000000007;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
struct fast_io {
  fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
  }
} fast_io_;
template <typename T>
struct edge {
  int to;
  T cap;
  int rev;
};
template <typename T>
struct Graph {
  int n;
  vector<vector<edge<T>>> vec;
  vector<int> level;
  vector<int> iter;
  Graph(int n) : n(n) {
    vec.resize(n);
    level.resize(n);
    iter.resize(n);
  }
  void adde(int at, int to, T cap) {
    vec[at].push_back((edge<T>){to, cap, (int)vec[to].size()});
    vec[to].push_back((edge<T>){at, 0, (int)vec[at].size() - 1});
  }
  void bfs(int s) {
    fill(level.begin(), level.end(), -1);
    level[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      auto p = q.front();
      q.pop();
      for (auto e : vec[p]) {
        if (level[e.to] < 0 && e.cap > 0) {
          level[e.to] = level[p] + 1;
          q.push(e.to);
        }
      }
    }
  }
  T dfs(int v, int t, T f) {
    if (v == t) return f;
    int st = iter[v];
    for (int i = st; i < vec[v].size(); i++) {
      iter[v] = i;
      auto &e = vec[v][i];
      if (level[v] < level[e.to] && e.cap > 0) {
        auto d = dfs(e.to, t, min(f, e.cap));
        if (d > 0) {
          e.cap -= d;
          vec[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
  T max_flow(int s, int t) {
    T flow = 0;
    while (true) {
      bfs(s);
      if (level[t] < 0) return flow;
      fill(iter.begin(), iter.end(), 0);
      T inf = numeric_limits<T>::max();
      T f = dfs(s, t, inf);
      while (f > 0) {
        flow += f;
        f = dfs(s, t, inf);
      }
    }
  }
  T min_cut(int s, int t) { return max_flow(s, t); }
};
using GraphI = Graph<int>;
using GraphL = Graph<long long>;
template <typename T>
T power(T a, T n, T mod) {
  T res = 1;
  T tmp = n;
  T curr = a;
  while (tmp) {
    if (tmp % 2 == 1) {
      res = (T)(res * curr % mod);
    }
    curr = (T)(curr * curr % mod);
    tmp >>= 1;
  }
  return res;
}
template <typename T>
bool suspect(T a, int s, T d, T n) {
  T x = power<T>(a, d, n);
  if (x == 1) return true;
  for (int r = 0; r < s; r++) {
    if (x == n - 1) return true;
    x = x * x % n;
  }
  return false;
}
template <typename T>
bool millar_rabin(T n) {
  if (n <= 1 || (n > 2 && n % 2 == 0)) return false;
  vector<ll> test = {2, 3, 5, 7, 11, 13, 17, 19, 23};
  T d = n - 1;
  int s = 0;
  while (d % 2 == 0) s++, d /= 2;
  for (int i = 0; i < test.size() && test[i] < n; i++) {
    if (!suspect<T>(test[i], s, d, n)) return false;
  }
  return true;
}
int main(int argc, char const *argv[]) {
  ll n, k;
  cin >> n >> k;
  vector<ll> p(n), c(n), l(n);
  for (int i = (0); i < (n); ++i) cin >> c[i] >> p[i] >> l[i];
  p.emplace_back(1);
  c.emplace_back(0);
  ll ld = 0, rd = n + 1;
  while (rd - ld > 1) {
    ll md = (rd + ld) / 2;
    ll one = -1;
    vector<int> odd, even;
    for (int i = (0); i < (n); ++i) {
      if (l[i] <= md) {
        if (p[i] == 1)
          chmax(one, c[i]);
        else if (p[i] & 1)
          odd.emplace_back(i);
        else
          even.emplace_back(i);
      }
    }
    if (one >= 0) {
      odd.emplace_back(n);
      c[n] = one;
    }
    ll tmp = 0;
    if (((int)(odd).size()) == 0 && ((int)(even).size()) == 0)
      tmp = 0;
    else if (((int)(odd).size()) == 0) {
      for (auto e : even) tmp += c[e];
    } else if (((int)(even).size()) == 0) {
      for (auto e : odd) tmp += c[e];
    } else {
      GraphL g(2 + ((int)(odd).size()) + ((int)(even).size()));
      for (int i = (0); i < (((int)(odd).size())); ++i)
        g.adde(0, 1 + i, c[odd[i]]);
      for (int i = (0); i < (((int)(even).size())); ++i)
        g.adde(1 + ((int)(odd).size()) + i,
               1 + ((int)(odd).size()) + ((int)(even).size()), c[even[i]]);
      for (int i = (0); i < (((int)(odd).size())); ++i) {
        for (int j = (0); j < (((int)(even).size())); ++j) {
          if (millar_rabin(p[even[j]] + p[odd[i]])) {
            g.adde(1 + i, 1 + ((int)(odd).size()) + j, linf);
          }
        }
      }
      tmp = -g.max_flow(0, 1 + ((int)(odd).size()) + ((int)(even).size()));
      for (int i = (0); i < (((int)(odd).size())); ++i) {
        tmp += c[odd[i]];
      }
      for (int i = (0); i < (((int)(even).size())); ++i) {
        tmp += c[even[i]];
      }
    }
    if (tmp >= k)
      rd = md;
    else
      ld = md;
  }
  cout << (rd == n + 1 ? -1 : rd) << endl;
  return 0;
}
