#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const int MAXM = 400010;
const int INF = 0x3f3f3f3f;
struct Edge {
  int to, next, cap, flow;
} edge[MAXM];
int tol;
int head[MAXN];
int gap[MAXN], dep[MAXN], pre[MAXN], cur[MAXN];
void init() {
  tol = 0;
  memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int w, int rw = 0) {
  edge[tol].to = v;
  edge[tol].cap = w;
  edge[tol].next = head[u];
  edge[tol].flow = 0;
  head[u] = tol++;
  edge[tol].to = u;
  edge[tol].cap = rw;
  edge[tol].next = head[v];
  edge[tol].flow = 0;
  head[v] = tol++;
}
int sap(int start, int end, int N) {
  memset(gap, 0, sizeof(gap));
  memset(dep, 0, sizeof(dep));
  memcpy(cur, head, sizeof(head));
  int u = start;
  pre[u] = -1;
  gap[0] = N;
  int ans = 0;
  while (dep[start] < N) {
    if (u == end) {
      int Min = INF;
      for (int i = pre[u]; i != -1; i = pre[edge[i ^ 1].to])
        if (Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow;
      for (int i = pre[u]; i != -1; i = pre[edge[i ^ 1].to]) {
        edge[i].flow += Min;
        edge[i ^ 1].flow -= Min;
      }
      u = start;
      ans += Min;
      continue;
    }
    bool flag = false;
    int v;
    for (int i = cur[u]; i != -1; i = edge[i].next) {
      v = edge[i].to;
      if (edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u]) {
        flag = true;
        cur[u] = pre[v] = i;
        break;
      }
    }
    if (flag) {
      u = v;
      continue;
    }
    int Min = N;
    for (int i = head[u]; i != -1; i = edge[i].next)
      if (edge[i].cap - edge[i].flow && dep[edge[i].to] < Min) {
        Min = dep[edge[i].to];
        cur[u] = i;
      }
    gap[dep[u]]--;
    if (!gap[dep[u]]) return ans;
    dep[u] = Min + 1;
    gap[dep[u]]++;
    if (u != start) u = edge[pre[u] ^ 1].to;
  }
  return ans;
}
struct node {
  int u, v, w;
  node() {}
  node(int u, int v, int w) : u(u), v(v), w(w) {}
  bool operator<(const node& a) const { return w < a.w; }
};
node f[205];
int n, k;
bool pr(int a) {
  if (a == 2) return 1;
  int b = sqrt(a);
  for (int i = 2; i <= b; i++) {
    if (a % i == 0) return 0;
  }
  return 1;
}
vector<node> vec;
bool com(node a, node b) { return a.u > b.u; }
bool check(int mid) {
  vec.clear();
  int ans = 0;
  init();
  set<int> s, s2;
  for (int i = 0; i < n; i++) {
    if (f[i].w > mid) break;
    if (f[i].v == 1) {
      vec.push_back(f[i]);
      vec.back().w = i;
      continue;
    }
    ans += f[i].u;
    if (f[i].v % 2) {
      for (int j = 0; j < n; j++) {
        if (f[j].w > mid) break;
        if (f[j].v % 2) continue;
        if (pr(f[i].v + f[j].v)) {
          if (s2.count(i + 1) == 0) {
            addedge(0, i + 1, f[i].u);
            s2.insert(i + 1);
          }
          addedge(i + 1, j + 1, 0x3f3f3f3f);
          if (s.count(j + 1) == 0) {
            addedge(j + 1, n + 1, f[j].u);
            s.insert(j + 1);
          }
        }
      }
    }
  }
  sort(vec.begin(), vec.end(), com);
  if (vec.size()) {
    ans += vec[0].u;
    int j = vec.back().w;
    for (int i = 0; i < n; i++) {
      if (f[i].w > mid) break;
      if (i == j) continue;
      if (f[i].v % 2) continue;
      if (pr(1 + f[i].v)) {
        if (s2.count(j + 1) == 0) {
          addedge(0, j + 1, vec[0].u);
          s2.insert(j + 1);
        }
        addedge(j + 1, i + 1, 0x3f3f3f3f);
        if (s.count(i + 1) == 0) {
          addedge(i + 1, n + 1, f[i].u);
          s.insert(i + 1);
        }
      }
    }
  }
  int p = ans - sap(0, n + 1, n + 2);
  return p >= k;
}
int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> f[i].u >> f[i].v >> f[i].w;
  }
  sort(f, f + n);
  int l = 0, r = f[n - 1].w;
  int ans = -1;
  while (l <= r) {
    int mid = l + r >> 1;
    if (check(mid)) {
      ans = mid;
      r = mid - 1;
    } else
      l = mid + 1;
  }
  cout << ans << endl;
  return 0;
}
