#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int MAXM = 20000;
const int INF = 0x3f3f3f3f;
struct Card {
  int p, c, l;
} cs[110];
bool be_prim[200004];
void doprim() {
  memset(be_prim, true, sizeof(be_prim));
  be_prim[0] = be_prim[1] = false;
  for (int i = 2; i < 200004; i++) {
    if (be_prim[i]) {
      for (long long j = (long long)i * i; j < 200004; j += i)
        be_prim[j] = false;
    }
  }
}
struct Edge {
  int to, nexts, cap, flow;
} edge[MAXM];
int tol;
int head[MAXN];
int gap[MAXN], dep[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].flow = 0;
  edge[tol].nexts = head[u];
  head[u] = tol++;
  edge[tol].to = u;
  edge[tol].cap = rw;
  edge[tol].flow = 0;
  edge[tol].nexts = head[v];
  head[v] = tol++;
}
int Q[MAXN];
void BFS(int start, int ends) {
  memset(dep, -1, sizeof(dep));
  memset(gap, 0, sizeof(gap));
  gap[0] = 1;
  int fronts = 0, rear = 0;
  dep[ends] = 0;
  Q[rear++] = ends;
  while (fronts != rear) {
    int u = Q[fronts++];
    for (int i = head[u]; i != -1; i = edge[i].nexts) {
      int v = edge[i].to;
      if (dep[v] != -1) continue;
      Q[rear++] = v;
      dep[v] = dep[u] + 1;
      gap[dep[v]]++;
    }
  }
}
int S[MAXN];
int sap(int start, int ends, int N) {
  BFS(start, ends);
  memcpy(cur, head, sizeof(head));
  int top = 0;
  int u = start;
  int ans = 0;
  while (dep[start] < N) {
    if (u == ends) {
      int Min = INF;
      int inser;
      for (int i = 0; i < top; i++) {
        if (Min > edge[S[i]].cap - edge[S[i]].flow) {
          Min = edge[S[i]].cap - edge[S[i]].flow;
          inser = i;
        }
      }
      for (int i = 0; i < top; i++) {
        edge[S[i]].flow += Min;
        edge[S[i] ^ 1].flow -= Min;
      }
      ans += Min;
      top = inser;
      u = edge[S[top] ^ 1].to;
      continue;
    }
    bool flag = false;
    int v;
    for (int i = cur[u]; i != -1; i = edge[i].nexts) {
      v = edge[i].to;
      if (edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u]) {
        flag = true;
        cur[u] = i;
        break;
      }
    }
    if (flag) {
      S[top++] = cur[u];
      u = v;
      continue;
    }
    int Min = N;
    for (int i = head[u]; i != -1; i = edge[i].nexts) {
      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[S[--top] ^ 1].to;
  }
  return ans;
}
bool cmp(const Card &a, const Card &b) { return a.l < b.l; }
int id[110];
int main() {
  doprim();
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d%d%d", &cs[i].p, &cs[i].c, &cs[i].l);
  int le = 1, ri = n, ans = -1;
  int s = 0, t = MAXN - 1;
  for (int i = 0; i < 50; i++) {
    int mid = (le + ri) >> 1;
    init();
    int pt = 1;
    int max1 = -1, ids = -1;
    int sum = 0;
    for (int j = 0; j < n; j++) {
      if (cs[j].l <= mid) {
        if (cs[j].c == 1) {
          if (cs[j].p > max1) {
            max1 = cs[j].p;
            ids = j;
          }
          id[j] = -1;
        } else {
          id[j] = pt++;
          sum += cs[j].p;
        }
      } else
        id[j] = -1;
    }
    if (ids >= 0) {
      id[ids] = pt++;
      sum += max1;
    }
    for (int j1 = 0; j1 < n; j1++) {
      if (id[j1] >= 0) {
        if (cs[j1].c % 2) {
          addedge(s, id[j1], cs[j1].p);
          for (int j2 = 0; j2 < n; j2++) {
            if (id[j2] >= 0 && be_prim[cs[j1].c + cs[j2].c])
              addedge(id[j1], id[j2], INF);
          }
        } else
          addedge(id[j1], t, cs[j1].p);
      }
    }
    if (sum - sap(s, t, pt + 1) >= k)
      ri = mid, ans = mid;
    else
      le = mid + 1;
  }
  printf("%d\n", ans);
  return 0;
}
