#include <bits/stdc++.h>
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long qmul(long long a, long long b, long long m) {
  long long res = 0;
  while (b) {
    if (b & 1) res = (res + a) % m;
    a = (a << 1) % m;
    b = b >> 1;
  }
  return res;
}
inline long long qpow(long long a, long long b, long long m) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % m;
    a = (a * a) % m;
    b = b >> 1;
  }
  return res;
}
inline long long inv(long long x, long long q) { return qpow(x, q - 2, q); }
using namespace std;
const int N = 300;
const int M = 1e4 + 10;
int dis[N];
struct edge {
  int np, f, ne;
};
edge ed[M];
int head[N];
int si;
void add(int u, int v, int f) {
  ed[si] = edge{v, f, head[u]};
  head[u] = si;
  si++;
}
bool bfs(int s, int tar) {
  memset(dis, 0, sizeof dis);
  queue<int> q;
  q.push(s);
  dis[s] = 1;
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (int i = head[cur]; i; i = ed[i].ne) {
      int np = ed[i].np;
      if (!dis[np] && ed[i].f) {
        dis[np] = dis[cur] + 1;
        q.push(np);
      }
    }
  }
  return dis[tar];
}
int dfs(int p, int flo, int tar) {
  if (p == tar) return flo;
  int delta = flo;
  for (int i = head[p]; i; i = ed[i].ne) {
    int np = ed[i].np;
    if (dis[p] + 1 == dis[np] && (ed[i].f)) {
      int d = dfs(np, min(delta, ed[i].f), tar);
      ed[i].f -= d;
      ed[i ^ 1].f += d;
      delta -= d;
    }
    if (delta == 0) break;
  }
  return flo - delta;
}
int dini(int n) {
  int ans = 0;
  while (bfs(1, n)) {
    ans += dfs(1, 0x3f3f3f3, n);
  }
  return ans;
}
bool ex[N];
struct node {
  int p, c, l;
};
bool cmp(const node& a, const node& b) { return a.l < b.l; }
node arr[N];
bool is_not_prime[500000];
long long build(int n, int num) {
  long long tot = 0;
  si = 2;
  memset(head, 0, sizeof head);
  bool exo = false;
  int onep = 0;
  int cnt = 2;
  for (int i = 1; i <= n; i++) {
    if (arr[i].c % 2) {
      if (arr[i].c == 1) {
        onep = max(onep, arr[i].p);
        exo = true;
        continue;
      } else {
        tot += arr[i].p;
        add(1, cnt, arr[i].p);
        add(cnt, 1, 0);
      }
    } else {
      tot += arr[i].p;
      add(cnt, num + 2, arr[i].p);
      add(num + 2, cnt, 0);
    }
    cnt++;
  }
  add(1, cnt, onep);
  add(cnt, 1, 0);
  tot += onep;
  int p1 = 2;
  for (int i = 1; i <= n; i++) {
    if (arr[i].c == 1) continue;
    int p2 = 2;
    for (int j = 1; j <= n; j++) {
      if (arr[j].c == 1) continue;
      if (j > i) {
        if (!is_not_prime[arr[i].c + arr[j].c]) {
          int tp1 = p1, tp2 = p2;
          if (arr[j].c % 2) swap(tp1, tp2);
          add(tp1, tp2, 0x3f3f3f3);
          add(tp2, tp1, 0);
        }
      }
      p2++;
    }
    p1++;
  }
  if (exo) {
    int p = 2;
    for (int i = 1; i <= n; i++) {
      if (arr[i].c == 1) continue;
      if (!is_not_prime[arr[i].c + 1]) {
        add(cnt, p, 0x3f3f3f3);
        add(p, cnt, 0);
      }
      p++;
    }
  }
  return tot;
}
void init() {
  for (int i = 2; i < 500000; i++) {
    if (is_not_prime[i]) continue;
    for (int j = 2 * i; j < 500000; j += i) {
      is_not_prime[j] = true;
    }
  }
}
int main() {
  std::ios::sync_with_stdio(0);
  init();
  int n, k;
  cin >> n >> k;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    int p, l, c;
    cin >> p >> c >> l;
    arr[i] = node{p, c, l};
  }
  sort(arr + 1, arr + n + 1, cmp);
  int l = 1, r = n;
  while (l <= r) {
    int mid = (l + r) / 2;
    int tot = build(mid, n);
    if (tot - dini(n + 2) >= k)
      r = mid - 1;
    else
      l = mid + 1;
  }
  if (l > n)
    cout << -1 << endl;
  else
    cout << arr[l].l << endl;
}
