#include <bits/stdc++.h>
using namespace std;
const int inf = 1e8;
struct card {
  int p, c, l;
} a[110];
int n, k;
bool mark[200010];
int cnt, head[110], to[40010], nxt[40010], v[40010];
int ans, dis[110], S, T;
void add(int x, int y, int z) {
  cnt++;
  to[cnt] = y;
  nxt[cnt] = head[x];
  head[x] = cnt;
  v[cnt] = z;
}
void ins(int x, int y, int z) {
  add(x, y, z);
  add(y, x, 0);
}
bool bfs() {
  queue<int> q;
  while (!q.empty()) {
    q.pop();
  }
  memset(dis, -1, sizeof(dis));
  dis[S] = 0;
  q.push(S);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    if (x == T) {
      return true;
    }
    for (int i = head[x]; i; i = nxt[i]) {
      int y = to[i];
      if (v[i] && dis[y] == -1) {
        dis[y] = dis[x] + 1;
        q.push(y);
      }
    }
  }
  return false;
}
int dfs(int x, int f) {
  int res = 0;
  if (x == T) {
    return f;
  }
  for (int i = head[x]; i; i = nxt[i]) {
    int y = to[i];
    if (v[i] && dis[y] == dis[x] + 1) {
      int tmp = dfs(y, min(f - res, v[i]));
      v[i] -= tmp;
      v[i ^ 1] += tmp;
      res += tmp;
      if (res == f) {
        return res;
      }
    }
  }
  if (!res) {
    dis[x] = -1;
  }
  return res;
}
void dinic() {
  ans = 0;
  while (bfs()) {
    ans += dfs(S, inf);
  }
}
int b[110], tot;
bool check(int x) {
  cnt = 1;
  tot = 0;
  memset(head, 0, sizeof(head));
  int cur = 0;
  for (int i = 0; i < n; i++) {
    if (a[i].l <= x) {
      b[++tot] = i;
      if (a[i].c == 1) {
        cur = max(cur, a[i].p);
      }
    }
  }
  T = tot + 1;
  int now = 0;
  for (int i = 1; i <= tot; i++) {
    if (a[b[i]].c == 1) {
      continue;
    }
    if (a[b[i]].c & 1) {
      ins(S, i, a[b[i]].p);
    } else {
      ins(i, T, a[b[i]].p);
    }
    now += a[b[i]].p;
    for (int j = i + 1; j <= tot; j++) {
      if (a[b[j]].c == 1) {
        continue;
      }
      if (!mark[a[b[i]].c + a[b[j]].c]) {
        if (a[b[i]].c & 1) {
          ins(i, j, inf);
        } else {
          ins(j, i, inf);
        }
      }
    }
  }
  if (cur) {
    ins(S, tot + 2, cur);
    now += cur;
    for (int i = 1; i <= tot; i++) {
      if (!mark[a[b[i]].c + 1] && a[b[i]].c != 1) {
        ins(tot + 2, i, inf);
      }
    }
  }
  dinic();
  now -= ans;
  return now >= k;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d%d%d", &a[i].p, &a[i].c, &a[i].l);
  }
  for (int i = 2; i <= 200000; i++) {
    if (mark[i]) {
      continue;
    }
    for (int j = i + i; j <= 200000; j += i) {
      mark[j] = true;
    }
  }
  int l = 1, r = n, mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid)) {
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  if (l > n) {
    puts("-1");
  } else {
    cout << l << endl;
  }
  return 0;
}
