#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
struct Edge {
  int a, b, cap, flow;
};
struct MaxFlow {
  int n, s, t;
  vector<int> d, ptr, q;
  vector<Edge> e;
  vector<vector<int> > g;
  int i, j;
  MaxFlow(int n) : n(n), d(n), ptr(n), q(n), g(n) {
    e.clear();
    for (i = 0; i < n; i++) {
      g[i].clear();
      ptr[i] = 0;
    }
  }
  void addEdge(int a, int b, int cap) {
    Edge e1 = {a, b, cap, 0};
    Edge e2 = {b, a, 0, 0};
    g[a].push_back((int)e.size());
    e.push_back(e1);
    g[b].push_back((int)e.size());
    e.push_back(e2);
  }
  int getMaxFlow(int _s, int _t) {
    s = _s;
    t = _t;
    int flow = 0;
    for (;;) {
      if (!bfs()) break;
      for (i = 0; i < n; i++) ptr[i] = 0;
      while (int pushed = dfs(s, INF)) flow += pushed;
    }
    return flow;
  }

 private:
  bool bfs() {
    int qh = 0, qt = 0;
    q[qt++] = s;
    for (i = 0; i < n; i++) d[i] = -1;
    d[s] = 0;
    while (qh < qt && d[t] == -1) {
      int v = q[qh++];
      for (i = 0; i < g[v].size(); i++) {
        int id = g[v][i], to = e[id].b;
        if (d[to] == -1 && e[id].flow < e[id].cap) {
          q[qt++] = to;
          d[to] = d[v] + 1;
        }
      }
    }
    return d[t] != -1;
  }
  int dfs(int v, int flow) {
    if (!flow) return 0;
    if (v == t) return flow;
    for (; ptr[v] < (int)g[v].size(); ++ptr[v]) {
      int id = g[v][ptr[v]], to = e[id].b;
      if (d[to] != d[v] + 1) continue;
      int pushed = dfs(to, min(flow, e[id].cap - e[id].flow));
      if (pushed) {
        e[id].flow += pushed;
        e[id ^ 1].flow -= pushed;
        return pushed;
      }
    }
    return 0;
  }
};
int c[123], p[123], l[123];
int pr[223456];
vector<pair<int, int> > vec;
int check(int mid) {
  int i, sumi = 0, j;
  vector<int> po, pe, ce, co;
  int maxi = -1, valed, val;
  for (i = 0; i < vec.size(); i++) {
    if (vec[i].first > mid) {
      break;
    } else {
      val = vec[i].second;
      if (c[val] == 1) {
        if (p[val] > maxi) {
          valed = val;
          maxi = p[val];
        }
      } else if (c[val] % 2) {
        po.push_back(p[val]);
        co.push_back(c[val]);
        sumi += p[val];
      } else {
        pe.push_back(p[val]);
        ce.push_back(c[val]);
        sumi += p[val];
      }
    }
  }
  if (maxi != -1) {
    po.push_back(p[valed]);
    co.push_back(c[valed]);
    sumi += p[valed];
  }
  MaxFlow flow(500);
  int n = co.size();
  int m = ce.size();
  for (i = 0; i < co.size(); i++) {
    for (j = 0; j < ce.size(); j++) {
      if (pr[co[i] + ce[j]] == 0) {
        flow.addEdge(i, j + n, po[i] + pe[j]);
      }
    }
  }
  for (i = 0; i < co.size(); i++) {
    flow.addEdge(n + m, i, po[i]);
  }
  for (i = 0; i < ce.size(); i++) {
    flow.addEdge(i + n, n + m + 1, pe[i]);
  }
  val = flow.getMaxFlow(n + m, n + m + 1);
  return sumi - val;
}
int main() {
  std::ios::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  int i, j;
  for (i = 2; i * i <= 200002; i++) {
    if (pr[i]) continue;
    for (j = i * i; j <= 200002; j += i) {
      pr[j] = 1;
    }
  }
  for (i = 0; i < n; i++) {
    cin >> p[i] >> c[i] >> l[i];
    vec.push_back(make_pair(l[i], i));
  }
  sort(vec.begin(), vec.end());
  int low = 1;
  int high = n;
  int mid, ans = -1;
  while (low <= high) {
    mid = (low + high) / 2;
    if (check(mid) >= k) {
      ans = mid;
      high = mid - 1;
    } else
      low = mid + 1;
  }
  cout << ans << endl;
}
