#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int f = 1, x = 0;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = -1;
  } while (ch < '0' || ch > '9');
  do {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  return f * x;
}
const int MAXN = 100 + 10;
const int INF = 0x3f3f3f3f;
int n, k;
int p[MAXN], c[MAXN], l[MAXN];
int ans;
struct node {
  int to;
  int next;
  int cap;
} g[20000 + 10];
int head[20000 + 10], cnt = 1;
inline void addedge(int a, int b, int w) {
  ++cnt;
  g[cnt].to = b;
  g[cnt].next = head[a];
  head[a] = cnt;
  g[cnt].cap = w;
  return;
}
inline bool isprime(int x) {
  if (x < 2) return false;
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) return false;
  return true;
}
int S, T;
int dis[MAXN], cur[10000 + 10];
inline bool BFS(int S, int T) {
  queue<int> q;
  memset(dis, 0, sizeof(dis));
  q.push(S);
  dis[S] = 1;
  cur[S] = head[S];
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = g[i].next) {
      int v = g[i].to;
      if ((dis[v] == 0) && g[i].cap > 0) {
        cur[v] = head[v];
        dis[v] = dis[u] + 1;
        q.push(v);
      }
    }
  }
  return dis[T] > 0;
}
inline int dfs(int x, int flow) {
  int rest = 0;
  if (x == T || flow == 0) return flow;
  for (int &i = cur[x]; i && flow > rest; i = g[i].next) {
    int v = g[i].to;
    if (g[i].cap > 0 && (dis[v] == dis[x] + 1)) {
      int ff = dfs(v, min(flow - rest, g[i].cap));
      if (ff == 0)
        dis[v] = -1;
      else {
        g[i].cap -= ff;
        g[i ^ 1].cap += ff;
        rest += ff;
      }
    }
  }
  return rest;
}
inline int dinic(int S, int T) {
  int res = 0;
  while (BFS(S, T)) res += dfs(S, INF);
  return res;
}
inline bool check(int x) {
  S = n + 1, T = n + 2;
  memset(head, 0, sizeof(head));
  cnt = 1;
  int maxiv, maxi = 0;
  for (int i = 1; i <= n; i++) {
    if ((!(c[i] & 1)) || (l[i] > x)) continue;
    if (c[i] == 1) {
      if (p[i] > maxi) maxiv = i, maxi = p[i];
      continue;
    }
    for (int j = 1; j <= n; j++) {
      if ((c[j] & 1) || (l[j] > x)) continue;
      if (isprime(c[i] + c[j])) {
        addedge(i, j, INF);
        addedge(j, i, 0);
      }
    }
  }
  if (maxi) {
    addedge(S, maxiv, p[maxiv]);
    addedge(maxiv, S, 0);
    for (int i = 1; i <= n; i++) {
      if ((c[i] % 2 == 0) && (l[i] <= x) && (isprime(c[i] + c[maxiv])))
        addedge(maxiv, i, INF), addedge(i, maxiv, 0);
    }
  }
  int sum = p[maxiv];
  for (int i = 1; i <= n; i++) {
    if (l[i] > x || c[i] == 1) continue;
    sum += p[i];
    if (c[i] & 1)
      addedge(S, i, p[i]), addedge(i, S, 0);
    else
      addedge(i, T, p[i]), addedge(T, i, 0);
  }
  return sum - dinic(S, T) >= k;
}
int main() {
  n = read(), k = read();
  for (int i = 1; i <= n; i++) p[i] = read(), c[i] = read(), l[i] = read();
  ans = -1;
  for (int i = 1; i <= 100; i++) {
    if (check(i)) {
      ans = i;
      break;
    }
  }
  cout << ans << endl;
}
