#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
const int oo = 1e9;
struct edge {
  int u, v, cap, cost, nxt;
};
vector<edge> E;
long long cost[110];
int last[110], SOURCE, SINK, n, p[110], k;
void addEdge(int u, int v, int cap, int cost) {
  E.push_back(edge());
  E.back().u = u;
  E.back().v = v;
  E.back().cap = cap;
  E.back().cost = cost;
  E.back().nxt = last[u];
  last[u] = E.size() - 1;
}
void add(int u, int v, int cap, int cost) {
  addEdge(u, v, cap, cost);
  addEdge(v, u, 0, -cost);
}
bool getPath() {
  for (int i = 0; i <= n + 8; ++i) cost[i] = oo, p[i] = -1;
  cost[SOURCE] = 0;
  bool update = true;
  for (int it = 0; it <= n + 1 && update; ++it) {
    update = false;
    for (int i = 0; i < E.size(); ++i) {
      if (E[i].cap > 0 && cost[E[i].u] < oo &&
          cost[E[i].u] + E[i].cost < cost[E[i].v]) {
        update = true;
        p[E[i].v] = i;
        cost[E[i].v] = cost[E[i].u] + E[i].cost;
      }
    }
  }
  return cost[SINK] < oo;
}
bool isPrime[200011], vis[200011];
struct card {
  int p, c, l;
};
card c[110];
bool check(int mid) {
  E.clear();
  long long allSum = 0, mx = 0;
  int idx = -1;
  for (int i = 0; i < n; ++i) {
    if (c[i].c == 1 && c[i].l <= mid && c[i].p >= mx) mx = c[i].p, idx = i;
  }
  for (int i = 0; i < n; i++) {
    if (c[i].l > mid || (c[i].c == 1 && i != idx)) continue;
    allSum += c[i].p;
    if (c[i].c & 1) {
      add(SOURCE, i + 2, c[i].p, 0);
    } else {
      add(i + 2, SINK, c[i].p, 0);
    }
    for (int j = 0; (c[i].c & 1) && j < n; j++) {
      if (c[j].l > mid || c[j].c == 1 || !isPrime[c[i].c + c[j].c]) continue;
      add(i + 2, j + 2, oo, 0);
    }
  }
  long long mxFlow = 0;
  while (getPath()) {
    int mn = oo;
    int cur = p[SINK];
    while (cur != -1) {
      mn = min(mn, E[cur].cap);
      cur = p[E[cur].u];
    }
    mxFlow += mn;
    cur = p[SINK];
    while (cur != -1) {
      E[cur].cap -= mn;
      E[cur ^ 1].cap += mn;
      cur = p[E[cur].u];
    }
  }
  return allSum - mxFlow >= k;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d%d", &c[i].p, &c[i].c, &c[i].l);
  }
  SOURCE = 0;
  SINK = 1;
  for (int i = 2; i <= 200000; ++i) {
    if (vis[i]) continue;
    for (int j = i; j <= 200000; j += i) {
      vis[j] = 1;
    }
    isPrime[i] = true;
  }
  int lo = 1, hi = n, best = -1;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (check(mid)) {
      best = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  printf("%d\n", best);
  return 0;
}
