#include <bits/stdc++.h>
using namespace std;
int o[120], p[120], q[120], x[120], y[120], z[120];
bool b[300000], d[120][120];
int i, j, k, l, m, n, r, t, ll, rr, mid;
bool c, e;
inline bool checkprime(int x) {
  for (int i = 2; i * i <= x; i++)
    if (!(x % i)) return false;
  return true;
}
int main() {
  srand((int)time(0));
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%d%d%d", &x[i], &y[i], &z[i]);
  for (i = 2; i <= 200000; i++) b[i] = checkprime(i);
  ll = 1, rr = n + 1;
  while (ll < rr) {
    mid = (ll + rr) / 2;
    k = 0;
    for (i = 1; i <= n; i++)
      if (z[i] <= mid) k++, o[k] = i;
    memset(d, false, sizeof(d));
    for (i = 1; i <= k; i++)
      for (j = 1; j <= k; j++)
        if (!b[y[o[i]] + y[o[j]]]) d[i][j] = true;
    for (i = 1; i <= k; i++) p[i] = i;
    c = false;
    for (i = 1; i <= 500; i++) {
      for (j = 1; j <= k; j++) swap(p[rand() % k + 1], p[rand() % k + 1]);
      r = 0, t = 0;
      for (j = 1; j <= k; j++) {
        e = true;
        for (l = 1; l <= r; l++)
          if (!d[p[j]][q[l]]) {
            e = false;
            break;
          }
        if (e) r++, q[r] = p[j], t = t + x[o[p[j]]];
      }
      if (t >= m) {
        c = true;
        break;
      }
    }
    if (c)
      rr = mid;
    else
      ll = mid + 1;
  }
  if (ll <= n)
    printf("%d", ll);
  else
    printf("-1");
  return 0;
}
