#include <bits/stdc++.h>
using namespace std;
const int maxsN = 10010;
const int maxsM = 200010;
struct bian {
  int to;
  int up;
  long long w;
} b[maxsM];
int n, m, s, t, front[maxsN], l, ceng[maxsN], c[maxsN];
long long ans;
void lian(int x, int y, long long w) {
  b[l].up = front[x];
  b[l].to = y;
  b[l].w = w;
  front[x] = l;
  l++;
  b[l].up = front[y];
  b[l].to = x;
  front[y] = l;
  l++;
}
bool bfs() {
  queue<int> q;
  memset(ceng, 0, sizeof(ceng));
  ceng[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    for (int i = front[now]; i > -1; i = b[i].up) {
      if (ceng[b[i].to] == 0 && b[i].w > 0) {
        ceng[b[i].to] = ceng[now] + 1;
        q.push(b[i].to);
      }
    }
  }
  return ceng[t] <= 1 ? 0 : 1;
}
long long dfs(int o, long long mins) {
  if (o == t) {
    return mins;
  }
  long long mi = 0;
  for (int &i = c[o]; i > -1; i = b[i].up) {
    if (ceng[b[i].to] == ceng[o] + 1 && b[i].w != 0) {
      long long now = dfs(b[i].to, min(b[i].w, mins - mi));
      if (now != 0) {
        b[i].w -= now;
        b[i ^ 1].w += now;
        mi += now;
        if (mi == mins) break;
      }
    }
  }
  return mi;
}
void dinic() {
  while (bfs()) {
    memcpy(c, front, sizeof(c));
    ans += dfs(s, 2147483647);
  }
}
int k;
struct card {
  int p, c, l;
} C[110], a1[110], a2[110];
int num1, num2;
bool pd(int o) {
  for (int i = 2; i * i <= o; ++i) {
    if (o % i == 0) return 0;
  }
  return 1;
}
card one;
bool check(int o) {
  num1 = num2 = l = 0;
  ans = 0;
  one.c = 0;
  memset(front, -1, sizeof(front));
  memset(b, 0, sizeof(b));
  int now = 0;
  for (int i = 1; i <= n; ++i) {
    if (C[i].l <= o) {
      if (C[i].c == 1) {
        if (one.c == 0 || one.p < C[i].p) one = C[i];
      } else {
        if (C[i].c % 2 == 1) {
          a1[++num1] = C[i];
          now += C[i].p;
        } else {
          a2[++num2] = C[i];
          now += C[i].p;
        }
      }
    }
  }
  if (one.c == 1) {
    a1[++num1] = one;
    now += one.p;
  }
  s = num1 + num2 + 2;
  t = num1 + num2 + 1;
  for (int i = 1; i <= num1; ++i) {
    lian(s, i, a1[i].p);
  }
  for (int i = num1 + 1; i <= num1 + num2; ++i) {
    lian(i, t, a2[i - num1].p);
  }
  for (int i = 1; i <= num1; ++i) {
    for (int j = num1 + 1; j <= num1 + num2; ++j) {
      if (pd(a1[i].c + a2[j - num1].c)) {
        lian(i, j, 2147483647);
      }
    }
  }
  dinic();
  if (now - ans >= k) return 1;
  return 0;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d%d", &C[i].p, &C[i].c, &C[i].l);
  }
  for (int i = 1; i <= n; ++i) {
    if (check(i)) {
      printf("%d\n", i);
      return 0;
    }
  }
  printf("-1");
}
