#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / gcd(a, b)) * b;
}
template <class T, class X>
inline bool getbit(T a, X i) {
  T t = 1;
  return ((a & (t << i)) > 0);
}
template <class T, class X>
inline T setbit(T a, X i) {
  T t = 1;
  return (a | (t << i));
}
template <class T, class X>
inline T resetbit(T a, X i) {
  T t = 1;
  return (a & (~(t << i)));
}
inline long long getnum() {
  char c = getchar();
  long long num, sign = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (num = 0; c >= '0' && c <= '9';) {
    c -= '0';
    num = num * 10 + c;
    c = getchar();
  }
  return num * sign;
}
inline long long power(long long a, long long b) {
  long long multiply = 1;
  for (int i = (0); i < (b); i++) {
    multiply *= a;
  }
  return multiply;
}
struct Edge {
  int to, rev, f, cap;
};
class Dinic {
 public:
  int dist[200], q[200], work[200], src, dest;
  vector<Edge> graph[200];
  void init(int sz) {
    for (int i = (0); i < (sz + 1); i++) graph[i].clear();
  }
  void clearFlow(int sz) {
    for (int i = (0); i < (sz + 1); i++) {
      for (int j = (0); j < (graph[i].size()); j++) graph[i][j].f = 0;
    }
  }
  void addEdge(int s, int t, int cap) {
    Edge a = {t, (int)graph[t].size(), 0, cap};
    Edge b = {s, (int)graph[s].size(), 0, 0};
    graph[s].push_back(a);
    graph[t].push_back(b);
  }
  bool bfs() {
    memset(dist, -1, sizeof(dist));
    dist[src] = 0;
    int qt = 0;
    q[qt++] = src;
    for (int qh = 0; qh < qt; qh++) {
      int u = q[qh];
      for (int j = 0; j < graph[u].size(); j++) {
        Edge &e = graph[u][j];
        int v = e.to;
        if (dist[v] < 0 && e.f < e.cap) {
          dist[v] = dist[u] + 1;
          q[qt++] = v;
        }
      }
    }
    return dist[dest] >= 0;
  }
  int dfs(int u, int f) {
    if (u == dest) return f;
    for (int &i = work[u]; i < (int)graph[u].size(); i++) {
      Edge &e = graph[u][i];
      if (e.cap <= e.f) continue;
      int v = e.to;
      if (dist[v] == dist[u] + 1) {
        int df = dfs(v, min(f, e.cap - e.f));
        if (df > 0) {
          e.f += df;
          graph[v][e.rev].f -= df;
          return df;
        }
      }
    }
    return 0;
  }
  int maxFlow(int _src, int _dest) {
    src = _src;
    dest = _dest;
    int result = 0;
    while (bfs()) {
      fill(work, work + 200, 0);
      while (int delta = dfs(src, 2000000000)) result += delta;
    }
    return result;
  }
} network;
vector<int> primes;
bool status[200005 + 7], isprime[200005 + 7];
void sieve() {
  for (int i = 4; i < 200005; i += 2) status[i] = true;
  for (int i = 3; i <= sqrt(200005); i++) {
    if (!status[i]) {
      for (int j = i * i; j < 200005; j += i + i) status[j] = true;
    }
  }
  isprime[2] = true;
  primes.push_back(2);
  for (int i = (3); i < (200005); i++) {
    if (!status[i]) isprime[i] = true;
  }
}
int n, k, p, c, l;
int total;
struct info {
  int p, c, l;
};
vector<info> all, ones;
void edge(int x, int y) { cout << x << " " << y << "\n"; }
void buildNetwork(int vova) {
  int idx = -1, mx = -1;
  for (int i = (0); i < (ones.size()); i++) {
    if (ones[i].l <= vova) {
      if (mx < ones[i].p) {
        idx = i;
        mx = ones[i].p;
      }
    }
  }
  if (idx != -1) {
    all.push_back(ones[idx]);
  }
  int src = n, sink = n + 1;
  vector<int> l, r;
  for (int i = (0); i < (all.size()); i++) {
    auto it = all[i];
    if (it.l > vova) continue;
    if (it.c % 2)
      l.push_back(i);
    else
      r.push_back(i);
  }
  total = 0;
  for (int i = (0); i < (l.size()); i++)
    network.addEdge(src, l[i], all[l[i]].p), total += all[l[i]].p;
  for (int i = (0); i < (r.size()); i++)
    network.addEdge(r[i], sink, all[r[i]].p), total += all[r[i]].p;
  for (int i = (0); i < (l.size()); i++) {
    for (int j = (0); j < (r.size()); j++) {
      if (isprime[all[l[i]].c + all[r[j]].c]) {
        network.addEdge(l[i], r[j], 1e5);
      }
    }
  }
  if (idx != -1) all.pop_back();
}
void solve() {
  int low = 1, high = 100, ans = -1;
  while (low <= high) {
    int mid = (low + high) / 2;
    network.init(n + 5);
    buildNetwork(mid);
    int out = total - network.maxFlow(n, n + 1);
    if (out >= k) {
      ans = mid;
      high = mid - 1;
    } else
      low = mid + 1;
  }
  cout << ans << "\n";
}
int main() {
  int test, cases = 1;
  sieve();
  cin >> n >> k;
  for (int i = (1); i < (n + 1); i++) {
    cin >> p >> c >> l;
    if (c == 1)
      ones.push_back({p, c, l});
    else
      all.push_back({p, c, l});
  }
  solve();
  return 0;
}
