#include <bits/stdc++.h>
using namespace std;
const int N = 111;
const int V = N * 2;
const int inf = 1000000000;
struct Flow {
  struct edge {
    int to, cap, rev;
    edge(int to = 0, int cap = 0, int rev = 0) : to(to), cap(cap), rev(rev) {}
  };
  vector<edge> g[V];
  int level[V], iter[V];
  int S, T;
  void clear_graph(int s, int t) {
    S = s, T = t;
    for (int i = 0; i < V; i++) {
      g[i].clear();
    }
  }
  void add_edge(int from, int to, int cap) {
    g[from].push_back(edge(to, cap, g[to].size()));
    g[to].push_back(edge(from, 0, g[from].size() - 1));
  }
  bool bfs() {
    memset(level, -1, sizeof(level));
    queue<int> q;
    q.push(S);
    level[S] = 0;
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (int i = 0; i < g[v].size(); i++) {
        edge &e = g[v][i];
        if (e.cap && level[e.to] == -1) {
          level[e.to] = level[v] + 1;
          q.push(e.to);
        }
      }
    }
    return level[T] != -1;
  }
  int dfs(int v, int f) {
    if (v == T) {
      return f;
    }
    for (int &i = iter[v]; i < g[v].size(); i++) {
      edge &e = g[v][i];
      if (e.cap && level[e.to] == level[v] + 1) {
        int d = dfs(e.to, min(f, e.cap));
        if (d) {
          e.cap -= d;
          g[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
  int max_flow() {
    int ans = 0, f = 0;
    while (bfs()) {
      memset(iter, 0, sizeof(iter));
      while (true) {
        f = dfs(S, inf);
        if (f == 0) {
          break;
        }
        ans += f;
      }
    }
    return ans;
  }
};
Flow flow;
struct node {
  int x, y, z, id;
  node(int p = 0, int c = 0, int l = 0, int id = 0)
      : x(p), y(c), z(l), id(id) {}
};
vector<node> a[N];
node val[N];
bool isp[222222];
int n, k;
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    a[z].push_back(node(x, y, z, i));
    val[i] = node(x, y, z);
  }
  memset(isp, 1, sizeof(isp));
  isp[0] = isp[1] = 0;
  for (int i = 2; i < 222222; i++) {
    if (!isp[i]) {
      continue;
    }
    for (int j = i + i; j < 222222; j += i) {
      isp[j] = 0;
    }
  }
  flow.clear_graph(n + 1, n + 2);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (val[i].y % 2 == 1) {
        continue;
      }
      if (val[j].y % 2 == 0) {
        continue;
      }
      if (!isp[val[i].y + val[j].y]) {
        continue;
      }
      flow.add_edge(i, j, inf);
    }
  }
  int tot = 0;
  bool h1 = 0;
  int v1 = 0, id1 = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i].size() == 0) {
      continue;
    }
    for (int j = 0; j < a[i].size(); j++) {
      if (a[i][j].y == 1 && h1) {
        if (a[i][j].x > v1) {
          tot += a[i][j].x - v1;
          flow.add_edge(id1, n + 2, a[i][j].x - v1);
          v1 = a[i][j].x;
        }
        continue;
      }
      if (a[i][j].y == 1) {
        h1 = 1;
        v1 = a[i][j].x;
        id1 = a[i][j].id;
      }
      tot += a[i][j].x;
      if (a[i][j].y % 2 == 0) {
        flow.add_edge(n + 1, a[i][j].id, a[i][j].x);
      } else {
        flow.add_edge(a[i][j].id, n + 2, a[i][j].x);
      }
    }
    tot -= flow.max_flow();
    if (tot >= k) {
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}
