#include <bits/stdc++.h>
struct graph {
  struct edge {
    int to, cap, opp;
  };
  std::vector<edge> a[505];
  int n, s, t, dep[505], nxt[505], can[505];
  void add(int x, int y, int v) {
    int p = a[x].size(), q = a[y].size();
    a[x].push_back(edge{y, v, q});
    a[y].push_back(edge{x, 0, p});
  }
  int bfs(int s, int t) {
    std::queue<int> q;
    for (int i = 1; i <= n; i++) dep[i] = 0, nxt[i] = 1, can[i] = 0;
    q.push(s);
    dep[s] = 1;
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (int i = 0; i < a[v].size(); i++) {
        int u = a[v][i].to;
        if (!dep[u] && a[v][i].cap) dep[u] = dep[v] + 1, q.push(u);
      }
    }
    return dep[t];
  }
  int dfs(int v, int now) {
    if (!nxt[v]) now = 0;
    if (v == t || !now) return now;
    int ss = 0;
    for (int i = can[v]; i < a[v].size(); i++, can[v]++) {
      int u = a[v][i].to;
      if (dep[v] + 1 != dep[u] || !a[v][i].cap) continue;
      int k = dfs(u, std::min(now, a[v][i].cap));
      if (!k) continue;
      a[v][i].cap = a[v][i].cap - k;
      a[u][a[v][i].opp].cap = a[u][a[v][i].opp].cap + k;
      ss = ss + k;
      now = now - k;
      if (!now) {
        can[v]--;
        break;
      }
    }
    if (!ss) nxt[v] = 0;
    return ss;
  }
  int dinic(int ss, int tt) {
    s = ss, t = tt;
    int ans = 0;
    while (bfs(s, t)) ans = ans + dfs(s, 1000000000);
    return ans;
  }
  void clear() {
    for (int i = 1; i <= n; i++) a[i].clear();
    n = 0;
  }
};
graph g;
int n, k, p[105], c[105], l[105];
int isprime(int x) {
  if (x < 2) return 0;
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
int solve(int x) {
  g.clear();
  g.n = n + 2;
  int s = n + 1, t = n + 2;
  int y = 0, ss = 0;
  for (int i = 1; i <= n; i++)
    if (l[i] <= x && c[i] != 1 && c[i] % 2 == 1)
      for (int j = 1; j <= n; j++)
        if (l[j] <= x && c[j] != 1 && c[j] % 2 == 0)
          if (isprime(c[i] + c[j])) g.add(i, j, 1000000000);
  for (int i = 1; i <= n; i++)
    if (c[i] == 1 && l[i] <= x)
      if (p[y] < p[i]) y = i;
  for (int i = 1; i <= n; i++)
    if (c[i] != 1 && l[i] <= x && isprime(c[y] + c[i]) && c[i] % 2 == 0)
      g.add(y, i, 1000000000);
  for (int i = 1; i <= n; i++) {
    if (l[i] > x || c[i] == 1 && i != y) continue;
    if (c[i] % 2)
      g.add(s, i, p[i]);
    else
      g.add(i, t, p[i]);
    ss = ss + p[i];
  }
  int ans = g.dinic(s, t);
  return ss - ans;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d%d%d", &p[i], &c[i], &l[i]);
  for (int i = 1; i <= 100; i++)
    if (solve(i) >= k) return printf("%d\n", i), 0;
  puts("-1");
  return 0;
}
