#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, k;
struct card {
  int p, c, l;
  int id;
} a[200];
vector<card> one;
vector<card> q;
vector<pair<int, int> > v;
queue<int> Q;
int VIS[200];
int d[200];
int vis[200];
struct edge {
  int to, cap, re;
};
vector<edge> g[200];
long long sum;
bool cmp(card x, card y) {
  if (x.l == y.l)
    return x.p < y.p;
  else
    return x.l < y.l;
}
void insert(int x, int y, int z) {
  g[x].push_back(edge{y, z, (int)g[y].size()});
  g[y].push_back(edge{x, 0, (int)g[x].size() - 1});
}
void build(int val) {
  for (int i = 0; i <= n + 1; i++) g[i].clear();
  memset(VIS, 0, sizeof VIS);
  int pos = -1;
  if (one.size()) {
    for (int i = 0; i < one.size(); i++) {
      if (one[i].l <= val) {
        if (pos == -1 || one[i].p > one[pos].p) pos = i;
      }
    }
  }
  if (pos != -1) pos = one[pos].id;
  for (int i = 0; i < v.size(); i++) {
    pair<int, int> t = v[i];
    card x = a[t.first], y = a[t.second];
    if (x.c == 1 && t.first != pos) continue;
    if (y.c == 1 && t.second != pos) continue;
    if (x.l > val || y.l > val) continue;
    if (x.c % 2) {
      insert(t.first, t.second, inf);
      VIS[t.first] = VIS[t.second] = 1;
    } else {
      insert(t.second, t.first, inf);
      VIS[t.first] = VIS[t.second] = 1;
    }
  }
  for (int i = 1; i <= n; i++)
    if (VIS[i]) {
      if (a[i].c % 2) {
        insert(0, i, a[i].p);
      } else
        insert(i, n + 1, a[i].p);
    }
}
bool bfs() {
  while (Q.size()) Q.pop();
  Q.push(0);
  memset(d, 0x3f, sizeof d);
  memset(vis, 0, sizeof vis);
  d[0] = 0;
  vis[0] = 1;
  while (Q.size()) {
    int top = Q.front();
    Q.pop();
    for (int i = 0; i < g[top].size(); i++) {
      edge &t = g[top][i];
      if (t.cap > 0 && !vis[t.to]) {
        d[t.to] = d[top] + 1;
        vis[t.to] = 1;
        Q.push(t.to);
      }
    }
  }
  return d[n + 1] != inf;
}
int dfs(int x, int t, int f) {
  if (x == t || f == 0) return f;
  int flow = f;
  for (int i = 0; i < g[x].size(); i++) {
    edge &e = g[x][i];
    if (d[e.to] == d[x] + 1) {
      int ff = dfs(e.to, t, min(e.cap, f));
      if (ff) {
        e.cap -= ff;
        g[e.to][e.re].cap += ff;
        f -= ff;
        if (f == 0) break;
      }
    }
  }
  return flow - f;
}
bool check(int x) {
  long long res = 0, f = 0;
  while (bfs()) {
    f = dfs(0, n + 1, inf);
    res += f;
  }
  sum = 0;
  for (int i = 1; i <= n; i++)
    if (a[i].l <= x && a[i].c != 1) sum += a[i].p;
  int pos = -1;
  for (int i = 0; i < one.size(); i++) {
    if (one[i].l <= x) {
      if (pos == -1 || one[i].p > one[pos].p) pos = i;
    }
  }
  if (pos != -1) sum += one[pos].p;
  return sum - res >= k;
}
bool is_prime(int x) {
  int y = sqrt(x + 0.5);
  for (int i = 2; i <= y; i++) {
    if (x % i == 0) return 0;
  }
  return 1;
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    card &t = a[i];
    cin >> t.p >> t.c >> t.l;
    t.id = i;
    if (t.c == 1)
      one.push_back(t);
    else
      q.push_back(t);
  }
  sort(one.begin(), one.end(), cmp);
  sort(q.begin(), q.end(), cmp);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i - 1; j++) {
      if (is_prime(a[i].c + a[j].c)) {
        v.push_back(make_pair(i, j));
      }
    }
  int l = 1, r = n;
  int mid = 0;
  int ans = -1;
  while (l <= r) {
    mid = (l + r) >> 1;
    build(mid);
    if (check(mid)) {
      ans = mid;
      r = mid - 1;
    } else
      l = mid + 1;
  }
  cout << ans << endl;
  return 0;
}
