#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
const int inf = 1e9 + 7;
long long n, m, k;
struct node {
  int p, c, l;
  node(){};
} s[maxn];
bool cmp(node x, node y) { return x.l < y.l; }
bool cmp2(int x, int y) { return s[x].p > s[y].p; }
struct edge {
  int from, to;
  long long flow;
  edge() {}
  edge(int from, int to, long long flow) {
    this->from = from;
    this->to = to;
    this->flow = flow;
  }
};
vector<int> g[maxn];
vector<edge> e;
int dis[maxn];
long long ans = 0;
int startPoint, endPoint;
edge t[maxn];
int tto[maxn];
bool vis2[200005];
vector<int> tmp, one, two;
set<int> p;
inline void print() {
  for (int i = 0; i < one.size(); i++) {
    int to = tmp[one[i]];
    cout << to << "  " << s[to].c << "  " << s[to].p << endl;
  }
  puts("\n");
  for (int i = 0; i < two.size(); i++) {
    int to = tmp[two[i]];
    cout << to << "  " << s[to].c << "  " << s[to].p << endl;
  }
  puts("\n");
  return;
}
inline void add(int a, int b, long long c) {
  e.push_back(edge(a, b, c));
  e.push_back(edge(b, a, 0));
  int len = e.size();
  g[a].push_back(len - 2);
  g[b].push_back(len - 1);
  return;
}
bool bfs() {
  memset(dis, -1, sizeof(dis));
  queue<int> que;
  dis[startPoint] = 0;
  que.push(startPoint);
  bool flag = 0;
  while (!que.empty()) {
    int x = que.front();
    que.pop();
    int len = g[x].size();
    for (int i = 0; i < len; i++) {
      int toNum = g[x][i];
      int to = e[g[x][i]].to;
      long long flow = e[toNum].flow;
      if (flow > 0 && dis[to] == -1) {
        dis[to] = dis[x] + 1;
        que.push(to);
        if (to == endPoint) flag = 1;
      }
    }
  }
  return flag;
}
long long dfs(int x, long long flow) {
  if (x == endPoint || flow == 0) return flow;
  long long res = 0, f;
  int len = g[x].size();
  for (int i = 0; i < len; i++) {
    int toNum = g[x][i];
    int to = e[toNum].to;
    long long c = e[toNum].flow;
    if (dis[to] == dis[x] + 1 && c > 0) {
      f = dfs(to, min(flow, c));
      if (f <= 0) continue;
      e[toNum].flow -= f;
      e[toNum ^ 1].flow += f;
      res += f;
      flow -= f;
      if (flow == 0) break;
    }
  }
  return res;
}
void maxflow() {
  ans = 0;
  while (bfs()) {
    ans += dfs(startPoint, inf);
  }
}
inline bool find(int x) {
  if (p.find(x) == p.end())
    return true;
  else
    return false;
}
inline bool check(int x) {
  tmp.clear();
  one.clear(), two.clear();
  long long sum1 = 0, sum2 = 0;
  memset(tto, 0, sizeof(tto));
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    if (s[i].l <= x)
      tmp.push_back(i);
    else
      break;
  }
  vector<int> oone;
  int len = tmp.size();
  for (int i = 0; i < len; i++) {
    int to = tmp[i];
    if (s[to].c == 1) {
      oone.push_back(i);
      continue;
    }
    sum += s[to].p;
    if (s[to].c & 1)
      one.push_back(i);
    else
      two.push_back(i);
  }
  sort(oone.begin(), oone.end(), cmp2);
  if (oone.size() >= 1) {
    sum += s[tmp[oone[0]]].p;
    one.push_back(oone[0]);
    for (int i = 1; i < oone.size(); i++) two.push_back(oone[i]);
  }
  for (int i = 0; i < one.size(); i++) sum1 += s[tmp[one[i]]].p;
  startPoint = 0, endPoint = len * 2 + 1;
  e.clear();
  for (int i = startPoint; i <= endPoint; i++) g[i].clear();
  len = (one.size() + two.size());
  for (int i = 0; i < one.size(); i++) {
    int to = tmp[one[i]];
    add(startPoint, to, inf);
    add(to, to + len, s[to].p);
    int len2 = two.size();
    for (int j = 0; j < len2; j++) {
      int ttoo = tmp[two[j]];
      if (!find(s[to].c + s[ttoo].c)) add(to + len, ttoo, inf);
    }
  }
  int len2 = two.size();
  for (int i = 0; i < len2; i++) {
    add(tmp[two[i]], tmp[two[i]] + len, s[tmp[two[i]]].p);
    add(tmp[two[i]] + len, endPoint, inf);
  }
  if (sum1 >= m) return true;
  maxflow();
  ans = sum - ans;
  if (ans >= m)
    return true;
  else
    return false;
}
int main() {
  for (int i = 2; i <= 200000; i++) {
    if (!vis2[i]) {
      p.insert(i);
      for (int j = i; j <= 200000; j += i) {
        vis2[j] = 1;
      }
    }
  }
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &s[i].p, &s[i].c, &s[i].l);
  }
  sort(s + 1, s + 1 + n, cmp);
  int l = 1, r = n;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  printf("%d", l > n ? -1 : l);
  return 0;
}
